Implement Magic Dictionary (Medium 676)

Implement a magic directory withbuildDict, andsearchmethods.

For the methodbuildDict, you'll be given a list of non-repetitive words to build a dictionary.

For the methodsearch, you'll be given a word, and judge whether if you modifyexactlyone character intoanothercharacter in this word, the modified word is in the dictionary you just built.

Example:

Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False

Note:

1 You may assume that all the inputs are consist of lowercase lettersa-z

2 For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.

3 Please remember to

RESET

your class variables declared in class MagicDictionary, as static/class variables are

persisted across multiple test cases

class MagicDictionary {
    Set<String> dictSet = null;

    /** Initialize your data structure here. */
    public MagicDictionary() {
        dictSet = new HashSet<String>();
    }

    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        for(String word : dict) {
            dictSet.add(word);    
        }
    }

    /** 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) {
        for (int j = 0; j < word.length(); j++) {
            char[] letters = word.toCharArray();
            char ch = letters[j];
            for (char k = 'a'; k <= 'z'; k++) {
                letters[j] = k;

                String word1 = new String(letters);
                // check if the modified word present in the dict
                // and it's not the same as the input word
                if (dictSet.contains(word1) && !word1.equals(word))
                    return true;

                letters[j] = ch; // reset the word for next change
            }
        }
        return false;
    }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dict);
 * boolean param_2 = obj.search(word);
 */