Trie Tree Method using JAVA!


  • 0
    T
    class MagicDictionary {
    
        /** Initialize your data structure here. */
        class TrieNode{
            String str;
            TrieNode[] children;
            TrieNode(){
                children = new TrieNode[26];
            }
            
        }
        TrieNode root;
        public MagicDictionary() {
            root = new TrieNode();
        }
        
        /** Build a dictionary through a list of words */
        public void buildDict(String[] dict) {
            for(String ele:dict){
                buildTree(ele,root);
            }
        }
        
        public void buildTree(String str,TrieNode root){
            char[] array = str.toCharArray();
            TrieNode current = root;
            for(int i=0;i<array.length;i++){
                char c = array[i];
                if(current.children[c-'a']==null){
                    current.children[c-'a'] = new TrieNode();
                }
                current = current.children[c-'a'];
            }
            current.str = str;
        }
        
        /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
        public boolean search(String word) {
            char[] array = word.toCharArray();
            for(int i=0;i<array.length;i++){
                char original = array[i];
                for(char c = 'a';c<='z';c++){
                    if(c!=original){
                        array[i] = c;
                        if(searchHelper(array,root)){
                            return true;
                        }
                    }
                }
                
                array[i] = original;
            }
            return false;
        }
        
        public boolean searchHelper(char[] array,TrieNode root){
            TrieNode current = root;
            for(int i=0;i<array.length;i++){
                char c = array[i];
                if(current.children[c-'a']==null){
                    return false;
                }
                current = current.children[c-'a'];
            }
            
            return current.str!=null;
        }
    }
    
    /**
     * Your MagicDictionary object will be instantiated and called as such:
     * MagicDictionary obj = new MagicDictionary();
     * obj.buildDict(dict);
     * boolean param_2 = obj.search(word);
     */
    
    

  • 0
    R

    @tiandiao123 Good solution. Just needed to improve a little bit in searchHelper method so that whenever needed to search the word, just check the remain characters not search the complete word from the start!


Log in to reply
 

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