https://leetcode.com/problems/add-and-search-word-data-structure-design/

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
public class WordDictionary {
private TrieNode root = new TrieNode();
private static class TrieNode {
// declared static since don't need to refer any member of parent class
boolean isEndOfWord;
TrieNode[] children;
public TrieNode() {
isEndOfWord = false;
children = new TrieNode[26];
}
}
// Adds a word into the data structure.
public void addWord(String word) {
TrieNode cur = root;
for (char c : word.toCharArray()) {
if (cur.children[c - 'a'] == null) {
cur.children[c - 'a'] = new TrieNode();
}
cur = cur.children[c - 'a'];
}
cur.isEndOfWord = true;
}
// Returns if the word is in the data structure. A word could
// contain the dot character '.' to represent any one letter.
public boolean search(String word) {
return search (word, root);
}
public boolean search(String word, TrieNode root) {
// search for word start from cur TrieNode
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (c == '.') { // skip current node
for (TrieNode child : cur.children) {
// try every child of the children of current node
// if any of them is true, then return true
if (child != null) {
if (search(word.substring(i + 1), child)) {
return true;
}
}
}
return false;
} else {
if (cur.children[c - 'a'] == null) {
return false;
}
cur = cur.children[c - 'a'];
}
}
return cur.isEndOfWord;
}
}
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");