208. Implement Trie (Prefix Tree)

mplement a trie with insert, search, and startsWith methods.

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

Solution:

If you don't know what is Trie, check its wiki.

It is a very good OO design problem. I create a TrieNode to maintain the current character and list of TrieNode children and the corresponding word if the current character is the end of the word. Since we only have letter a-z in the word, so we can use a TrieNode array with length of 26 to track its children. While we insert a word, we check if current trie level has an existing trieNode with the same character, if so we use the existing TrieNode, if not, we create a new one and add it to the children list of its parent TrieNode. 

Make sure to mark the word when it process the last character of the word, so we can check if it is prefix or completed word when we do search.

 public class Trie {  
    public TrieNode head;  
   public class TrieNode{  
     public char c;  
     public TrieNode[] children;  
     public String word;  
     public TrieNode(char h){  
       c=h;  
       children=new TrieNode[26];  
       word=null;  
     }  
   }  
   /** Initialize your data structure here. */  
   public Trie() {  
     head=new TrieNode('#');  
   }  
   /** Inserts a word into the trie. */  
   public void insert(String word) {  
     TrieNode cur=head;  
     for(int i=0;i<word.length();i++){  
       int ind=word.charAt(i)-'a';  
       if(cur.children[ind]==null){  
         TrieNode next=new TrieNode(word.charAt(i));  
         cur.children[ind]=next;  
       }  
       cur=cur.children[ind];  
     }  
     cur.word=word;  
   }  
   /** Returns if the word is in the trie. */  
   public boolean search(String word) {  
     TrieNode cur=head;  
     for(int i=0;i<word.length();i++){  
       int ind=word.charAt(i)-'a';  
       cur=cur.children[ind];  
       if(cur==null) return false;  
     }  
     return cur.word!=null;  
   }  
   /** Returns if there is any word in the trie that starts with the given prefix. */  
   public boolean startsWith(String prefix) {  
     TrieNode cur=head;  
     for(int i=0;i<prefix.length();i++){  
       int ind=prefix.charAt(i)-'a';  
       cur=cur.children[ind];  
       if(cur==null) return false;  
     }  
     return true;  
   }  
 }  
 /**  
  * Your Trie object will be instantiated and called as such:  
  * Trie obj = new Trie();  
  * obj.insert(word);  
  * boolean param_2 = obj.search(word);  
  * boolean param_3 = obj.startsWith(prefix);  
  */