211. Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Solution

Use prefix tree (Trie) 

Everything is the same except this one has a wild match '.' which requires us to iterate all the possible children trienodes of current TrieNode, return true if any of its child returns true, otherwise return false.

 public class WordDictionary {  
   public TrieNode head;  
    public class TrieNode{  
      public char c;  
      public TrieNode[] children;  
      public boolean isEnd;  
      public TrieNode(char c){  
        c=c;  
        children=new TrieNode[26];  
        isEnd=false;  
      }  
    }  
   /** Initialize your data structure here. */  
   public WordDictionary() {  
    head=new TrieNode('#');  
   }  
   /** Adds a word into the data structure. */  
   public void addWord(String word) {  
     TrieNode cur=head;  
     for(int i=0;i<word.length();i++){  
       int ind=word.charAt(i)-'a';  
       if(cur.children[ind]==null){  
         cur.children[ind]=new TrieNode(word.charAt(i));  
       }  
       cur=cur.children[ind];  
     }  
     cur.isEnd=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 helper(word,0,head);  
   }    
   private boolean helper(String word,int i,TrieNode head){  
     TrieNode cur=head;  
     if(i==word.length()) return cur.isEnd;  
      if(word.charAt(i)!='.'){  
        int ind=word.charAt(i)-'a';  
         if(cur.children[ind]==null) return false;  
         else return helper(word,i+1,cur.children[ind]);  
      }  
      else{  
        for(int j=0;j<26;j++){  
          if(cur.children[j]!=null){  
            if(helper(word,i+1,cur.children[j])) 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);  
  */