Note: You may assume that all words are consist of lowercase letters a-z.
Solution:
class WordDictionary {
static class TrieNode {
char c;
List<TrieNode> children;
boolean isWord;
public TrieNode(char c) {
this.c = c;
children = new ArrayList();
isWord = false;
}
}
TrieNode root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new TrieNode('\0');
}
/** Adds a word into the data structure. */
public void addWord(String word) {
char[] arr = word.toCharArray();
TrieNode curr = root;
for (char c : arr) {
boolean found = false;
for (TrieNode child : curr.children) {
if (child.c == c) {
curr = child;
found = true;
break;
}
}
if (!found) {
TrieNode newNode = new TrieNode(c);
curr.children.add(newNode);
curr = newNode;
}
}
curr.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) {
for (TrieNode node : this.root.children) {
if (search(word, node)) {
return true;
}
}
return false;
}
private boolean search(String word, TrieNode root) {
char c = word.charAt(0);
TrieNode curr = root;
if (word.length() == 1) {
if ((curr.c == c || c == '.') && curr.isWord) return true;
return false;
}
if (c == '.') {
for (TrieNode child : curr.children) {
if (search(word.substring(1), child)) {
return true;
}
}
return false;
} else {
if (c != root.c) {
return false;
} else {
for (TrieNode child : root.children) {
if (search(word.substring(1), child)) {
return true;
}
}
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);
*/