Java Trie implementation, beats 95%


  • 0
    V
    public class WordDictionary 
    {
        class MyTrie
        {
            char val;
            MyTrie[] list;
            boolean isLast;
            MyTrie(char v)
            {
                isLast = false;
                val = v;
                list = new MyTrie[26];
            }
        }
        MyTrie[] myRoot;
        boolean isDone;
        /** Initialize your data structure here. */
        public WordDictionary() 
        {
            isDone = false;
            myRoot = new MyTrie[26];
        }
        
        /** Adds a word into the data structure. */
        public void addWord(String word) 
        {
            MyTrie[] temp = myRoot;
            MyTrie curr = null;
            char c;
            for(int i = 0; i < word.length(); i++)
            {
                c = word.charAt(i);
                if(temp[c - 97] == null)
                {
                    curr = new MyTrie(c);
                    temp[c - 97] = curr;
                }
                else
                    curr = temp[c - 97];
                temp = curr.list;
            }
            curr.isLast = true;        
        }
        void dfs(String word, int ind, MyTrie[] myRoot, MyTrie prev)
        {
            if(ind >= word.length())
            {
                if(prev != null)
                    isDone = prev.isLast;
                else
                    isDone = true;
                return;
            }
            char c = word.charAt(ind);
            if(c != '.')
            {
                if(myRoot[c - 97] == null || myRoot[c - 97].val != c)
                    return;
                dfs(word, ind + 1, myRoot[c - 97].list, myRoot[c - 97]);
                return;
            }
            for(int i = 0; i < 26 && !isDone; i++)
            {
                if(myRoot[i] == null)
                    continue;
                dfs(word, ind + 1, myRoot[i].list, myRoot[i]);
            }
        }
        /** 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) 
        {
            isDone = false;
            dfs(word, 0, myRoot, null);
            return isDone;
        }
    }
    
    /**
     * Your WordDictionary object will be instantiated and called as such:
     * WordDictionary obj = new WordDictionary();
     * obj.addWord(word);
     * boolean param_2 = obj.search(word);
     */

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.