> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0676-implement-magic-dictionary.md).

# 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

```java
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);
 */
```