211. Add and Search Word - Data structure design
Trie 的 recursive 写法。
class TrieNode {
boolean isWord;
TrieNode[] children;
public TrieNode() {
isWord = false;
children = new TrieNode[26];
}
}
class WordDictionary {
TrieNode root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
int c = word.charAt(i) - 'a';
if (cur.children[c] == null) {
cur.children[c] = new TrieNode();
}
cur = cur.children[c];
}
cur.isWord = 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.toCharArray(), 0, root);
}
private boolean search(char[] cArray, int index, TrieNode node) {
if (index == cArray.length) {
return node.isWord;
}
if (cArray[index] == '.') {
for (int i = 0; i < node.children.length; i++) {
if (node.children[i] != null) {
if (search(cArray, index + 1, node.children[i])) {
return true;
}
}
}
} else {
return node.children[cArray[index] - 'a'] != null
&& search(cArray, index + 1, node.children[cArray[index] - 'a']);
}
return false;
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/