public class WordDictionary {
private TrieNode root = new TrieNode();
private static class TrieNode {
boolean isEndOfWord;
TrieNode[] children;
public TrieNode() {
isEndOfWord = false;
children = new TrieNode[26];
}
}
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;
}
public boolean search(String word) {
return search (word, root);
}
public boolean search(String word, TrieNode root) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (c == '.') {
for (TrieNode child : cur.children) {
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;
}
}