211. Add and Search Word - Data structure design
class WordDictionary {
private class TrieNode {
public boolean isWord;
public TrieNode[] children = new TrieNode[26];
}
private 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){
if(cur.children[word.charAt(i)-'a']==null){
cur.children[word.charAt(i)-'a']= new TrieNode();
}
cur=cur.children[word.charAt(i)-'a'];
}
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 match(root,word,0);
}
private boolean match(TrieNode root,String word, int index){
if(index == word.length()) return root.isWord;
if(word.charAt(index)!='.'){
return root.children[word.charAt(index)-'a']!=null && match(root.children[word.charAt(index)-'a'], word,index+1);
}else{
for(int i =0 ; i<26;++i){
if(root.children[i]==null) continue;
if(match(root.children[i], word,index+1)) 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);
*/