Simple Java - Using HashMap - 100 ms


  • 0
    R
    class MagicDictionary {
    
        Map<String, Character> map;
        /** Initialize your data structure here. */
        public MagicDictionary() {
            map = new HashMap<>();
        }
        
        /** Build a dictionary through a list of words */
        public void buildDict(String[] dict) {
            for(String each: dict){
                StringBuilder temp = new StringBuilder(each); 
                for(int i=0;i<each.length();i++){
                    temp.setCharAt(i,'*');
                    char c = each.charAt(i);
                    String key = temp.toString();
                    if(!map.containsKey(key)){
                        // Track the missing character
                        map.put(key,c);
                    }
                    else{
                        // If there exists more than one occurence update it as '*'
                        // If there exists more than one occurence then it is bound to return true.
                        map.put(key,'*');
                    }
                    temp.setCharAt(i,c);
                }
            }
        }
        
        /** 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) {
            StringBuilder newword = new StringBuilder(word);
            for(int i=0;i<word.length();i++){
                newword.setCharAt(i,'*');
                if(map.containsKey(newword.toString())){
                    char c = map.get(newword.toString());
                    if(c=='*' || c!=word.charAt(i))
                       return true;
                }
                newword.setCharAt(i, word.charAt(i));      
            }
            return false;
        }
    }
    

Log in to reply
 

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