0676. Implement Magic Dictionary

https://leetcode.com/problems/implement-magic-dictionary

Description

Design a data structure that is initialized with a list of different words. Provided a string, you should determine if you can change exactly one character in this string to match any word in the data structure.

Implement the MagicDictionary class:

• MagicDictionary() Initializes the object.

• void buildDict(String[] dictionary) Sets the data structure with an array of distinct strings dictionary.

• bool search(String searchWord) Returns true if you can change exactly one character in searchWord to match any string in the data structure, otherwise returns false.

Example 1:

**Input**
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
**Output**
[null, null, false, true, false, false]
**Explanation**
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // return False
magicDictionary.search("hhllo"); // We can change the second 'h' to 'e' to match "hello" so we return True
magicDictionary.search("hell"); // return False
magicDictionary.search("leetcoded"); // return False

Constraints:

• 1 <= dictionary.length <= 100

• 1 <= dictionary[i].length <= 100

• dictionary[i] consists of only lower-case English letters.

• All the strings in dictionary are distinct.

• 1 <= searchWord.length <= 100

• searchWord consists of only lower-case English letters.

• buildDict will be called only once before search.

• At most 100 calls will be made to search.

ac

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 word : dict) {
            build(word);
        }
    }
    private void build(String word) {
        TrieNode r = root;
        for (int i = 0; i < word.length(); i++) {
            int pos = word.charAt(i) - 'a';
            if (r.next[pos] == null) r.next[pos] = new TrieNode();
            r = r.next[pos];
        }
        r.isWord = 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) {
        return search2(root, word, 0, false);
    }
    private boolean search2(TrieNode node, String word, int start, boolean modified) {
        TrieNode r = node;
        for (int i = start; i < word.length(); i++) {
            int p = word.charAt(i) - 'a';

            if (!modified) {
                // try to modify one char
                for (int j = 0; j < 26; j++) {
                    if (j == p || r.next[j] == null) continue; // skip same character and null
                    if (search2(r.next[j], word, i+1, true)) return true;
                }
            }

            // can't find it in this position, move on
            if (r.next[p] == null) return false;
            r = r.next[p];
        }

        return r.isWord && modified;
    }
}

class TrieNode {
    TrieNode[] next;
    boolean isWord;
    public TrieNode() {
        next = new TrieNode[26];
    }
}

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