Using HashMap & HashSet


  • 0
    I

    I am building the dictionary as key pair values in HashMap<Integer, HashSet<String>>. Here key is the length of word. If we have two words like "hello", & "leetcode" then our HashMap will be like {5=[hello], 8=[leetcode]}. While searching if word length is not match with our dictionary key then return false other wise we will check with each character with our matched key's value that is HashSet and then we will iterate each string in HashSet with each character with given word.

    class MagicDictionary {
        
        HashMap<Integer, HashSet<String>> dictionary;
    
        /** Initialize your data structure here. */
        public MagicDictionary() {
            dictionary = new HashMap<Integer, HashSet<String>>();
        }
        
        /** Build a dictionary through a list of words */
        public void buildDict(String[] dict) {
            HashSet<String> tempDict;
            for(String s: dict){            
                tempDict = dictionary.get(s.length());
                if(tempDict == null){
                    tempDict = new HashSet();                
                    tempDict.add(s);
                }else{
                    tempDict.add(s);
                }
                
                dictionary.put(s.length(), tempDict);
            }
            
    
            
           
            
        }
        
        /** 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) {
            HashSet<String> tempDict;        
            tempDict = dictionary.get(word.length());
            boolean wordFound = false;
            String dicString = new String();
            int missingCharCount = 0;
            
            if(tempDict == null)        
            wordFound = false;
            else
            {
                Iterator wordsItr = tempDict.iterator();
                while(wordsItr.hasNext()){
                    dicString = (String) wordsItr.next();
                    missingCharCount = 0;                
                    for(int index = 0; index < dicString.length(); index++){                        
                        if(word.charAt(index) != dicString.charAt(index)){                                               
                            missingCharCount++;
                        }                    
                          if(missingCharCount == 2)
                              break;
                    }                
                    if(missingCharCount == 1) {
                        wordFound = true;
                        break;
                    }
                }            
            }
            
            return wordFound;
        }
    }
    
    

Log in to reply
 

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