-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathAddAndSearchWord.js
More file actions
68 lines (57 loc) · 1.55 KB
/
Copy pathAddAndSearchWord.js
File metadata and controls
68 lines (57 loc) · 1.55 KB
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
58
59
60
61
62
63
64
65
66
67
68
// https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/
class TrieNode {
constructor() {
this.children = {};
this.isEnd = false;
}
containsKey(char) {
return this.children[char] != undefined;
}
get(char) {
return this.children[char];
}
put(char, node) {
this.children[char] = node;
}
}
class WordDictionary {
constructor() {
this.root = new TrieNode();
}
addWord(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
const char = word[i];
if (!node.containsKey(char)) {
node.put(char, new TrieNode());
}
node = node.get(char);
}
node.isEnd = true;
}
search(word) {
return backTracing(word, this.root);
function backTracing(word, node) {
const char = word[0];
if (char == '.') {
for (const child of Object.values(node.children)) {
if (backTracing(word.slice(1), child)) return true;
}
return false;
}
else {
if (word.length == 0 && node.isEnd) return true;
if (!node.containsKey(char)) return false;
return backTracing(word.slice(1), node.get(char));
}
}
}
}
function test1() {
word = "word";
var obj = new WordDictionary()
obj.addWord(word)
// console.log(obj.search(word));
console.log(obj.search('.ord'));
}
test1();