211_Add_and_Search_Word.java

classWordDictionary {
classTrieNode {
privateTrieNode[] children;
privatebooleanisWord;

publicTrieNode() {
children = newTrieNode[26];
isWord = false;
 }
 }

privateTrieNoderoot;

publicWordDictionary() {
root = newTrieNode();
 }

publicvoidaddWord(Stringword) {
TrieNodecurr = root;

for (charc : word.toCharArray()) {
if (curr.children[c - 'a'] == null) {
curr.children[c - 'a'] = newTrieNode();
 }
curr = curr.children[c - 'a'];
 }

curr.isWord = true;
 }

publicbooleansearch(Stringword) {
returnhelper(word, 0, root);
 }

privatebooleanhelper(Stringword, intidx, TrieNodet) {
if (idx >= word.length()) {
returnt.isWord;
 }

charc = word.charAt(idx);

if (c == '.') {
for (inti = 0; i < 26; i++) {
if (t.children[i] != null && helper(word, idx + 1, t.children[i])) {
returntrue;
 }
 }

returnfalse;
 }

returnt.children[c - 'a'] != null && helper(word, idx + 1, t.children[c - 'a']);
 }
}