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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0676-implement-magic-dictionary.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.