Java Trie Tree Optimal Solution


  • 0
    R
    class MagicDictionary {
            TrieNode root;
    
        /** Initialize your data structure here. */
        public MagicDictionary() {
            root = new TrieNode();
        }
        
        /** Build a dictionary through a list of words */
        public void buildDict(String[] dict) {
            for (String s : dict){
                insert (s);
            }
        }
        
        public void insert (String s){
            TrieNode current = root;
            
            for (char c : s.toCharArray()){
                if (!current.children.containsKey(c)){
                    current.children.put(c , new TrieNode());
                } 
                current = current.children.get(c);
            }
            current.endOfWord = true;
        }
        
        /** 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) {
            TrieNode current = root;
            char [] array = word.toCharArray();
            
            for (int i=0; i<array.length; i++){
                char c = array[i];
                 for (char key: current.children.keySet()){
                    if (key != c  && helper(current.children.get(key) , array , i+1)){
                        return true;
                    }
                }
                if (current.children.containsKey(c)){
                    current = current.children.get(c);
                } else { 
                    return false;
                }
            }
             return false;
        }
        
        public boolean helper (TrieNode current , char [] array , int j){
            for (int i = j; i<array.length; i++){
                char c = array[i];
                if (!current.children.containsKey(c)){
                    return false;
                }
                current = current.children.get(c);
            }
            
            if (current.endOfWord == true){
                return true;
            } else return false;
        }
       
    }
    
     class TrieNode{
            HashMap <Character , TrieNode> children;
            boolean endOfWord;
            
            TrieNode (){
                children = new HashMap<>();
                endOfWord = false;
            }
        }
    

Log in to reply
 

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