-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_211.java
More file actions
49 lines (41 loc) · 1.34 KB
/
Copy pathP_211.java
File metadata and controls
49 lines (41 loc) · 1.34 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
package leetcode.medium;
@SuppressWarnings({ "unused", "InnerClassMayBeStatic", "PublicConstructorInNonPublicClass" })
public class P_211 {
class WordDictionary {
class Trie {
Trie[] children = new Trie[26];
boolean isWord;
}
Trie root;
public WordDictionary() {
root = new Trie();
}
public void addWord(String word) {
Trie iter = root;
for (char c : word.toCharArray()) {
if (iter.children[c - 'a'] == null) {
iter.children[c - 'a'] = new Trie();
}
iter = iter.children[c - 'a'];
}
iter.isWord = true;
}
public boolean search(String word) {
return dfs(word.toCharArray(), 0, root);
}
private boolean dfs(char[] w, int idx, Trie iter) {
if (iter == null) { return false; }
if (idx == w.length) { return iter.isWord; }
if (w[idx] == '.') {
for (Trie child : iter.children) {
if (dfs(w, idx + 1, child)) {
return true;
}
}
return false;
}
//noinspection TailRecursion
return dfs(w, idx + 1, iter.children[w[idx] - 'a']);
}
}
}