-
Notifications
You must be signed in to change notification settings - Fork 3
/
trie.html
57 lines (56 loc) · 1.16 KB
/
trie.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
</body>
<script>
class Trie {
constructor() {
this.root = Object.create(null)
}
insert(word) {
let node = this.root
for (let item of word) {
if (!node[item]) {
node[item] = Object.create(null)
}
node = node[item]
}
if (!('$' in node)) {
node['$'] = 0
}
node['$'] ++
}
max(word) {
let max = 0
let maxWord = ''
let visit = (node, word) => {
if (node.$ && (node.$ > max)) {
max = node.$
maxWord = word
}
for (let p in node) {
visit(node[p], word + p)
}
}
visit(this.root, '')
console.log(maxWord)
}
}
function randomWord(length) {
let s = ''
for (let i = 0; i < length; i ++) {
s += String.fromCharCode(Math.random() * 26 + 'a'.charCodeAt(0))
}
return s
}
let trie = new Trie()
for (let i = 0; i < 10000; i ++) {
trie.insert(randomWord(1))
}
</script>
</html>