Implement Magic Dictionary


  • 0

    Click here to see the full article post


  • 0
    L

    HashMap with length as Index, 95ms, and beat 100%.

    class MagicDictionary {

    private Map<Integer,List<String>> dicts = null;
    
    /** Initialize your data structure here. */
    public MagicDictionary() {
        
    }
    
    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        this.dicts = new HashMap<Integer,List<String>>();
        
        for(String d : dict){
            List<String> lst = this.dicts.get(d.length());
            if(lst == null){
                lst = new ArrayList<String>();
                this.dicts.put(d.length(), lst);
            }
            
            lst.add(d);
        }
    }
    
    /** 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) {
        int len = word.length();
        List<String> lst = this.dicts.get(len);
        if(lst != null){
            for(String d : lst){
                int diffCnt = 0;
                for(int i=0;i<len;i++){
                    if(d.charAt(i) != word.charAt(i)) diffCnt ++;
                }
                if(diffCnt==1) return true;
            }
        }
        return false;
    }
    

    }


  • 0
    M

    For Approach # 1, time complexity is O(n + k), where n is the length of words. Build the bucket only costs O(n) since word.length() costs O(1). Search costs O(k).
    Space complexity is also O(n), in the map, we only need to store the reference for each string, which is O(1) for each and totally O(n).


Log in to reply
 

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