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
| class WordDictionary {
private static class Node {
private final Node[] children;
private boolean end;
public Node() {
this.children = new Node[26];
}
}
private final Node root;
public WordDictionary() {
this.root = new Node();
}
public void addWord(String word) {
Node curr = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (curr.children[index] == null) {
curr.children[index] = new Node();
}
curr = curr.children[index];
}
curr.end = true;
}
public boolean search(String word) {
return dfs(root, word, 0);
}
private boolean dfs(Node node, String word, int index) {
if (index == word.length()) {
return node.end;
}
char c = word.charAt(index);
if (c == '.') {
for (int i = 0; i < node.children.length; i++) {
if (node.children[i] != null && dfs(node.children[i], word, index + 1)) {
return true;
}
}
return false;
} else {
int i = c - 'a';
return node.children[i] != null && dfs(node.children[i], word, index + 1);
}
}
}
|
注意搜索时需要匹配而不仅是前缀匹配，所以引入了 end 标志。
References
211. Design Add and Search Words Data Structure