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

# 676 Implement Magic Dictionary

## 676. [Implement Magic Dictionary](https://leetcode.com/problems/implement-magic-dictionary/description/)

## 1. Question

Implement a magic directory with`buildDict`, and`search`methods.

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

For the method`search`, you'll be given a word, and judge whether if you modify **exactly** one character into **another** character in this word, the modified word is in the dictionary you just built.

**Example 1:**

```
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 letters`a-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**. Please see [here](https://leetcode.com/faq/#different-output) for more details.

## 2. Implementation

**(1) HashMap**

```java
class MagicDictionary {
    Map <String, List<int[]>> map;
    /** Initialize your data structure here. */
    public MagicDictionary() {
        map = new HashMap<>();
    }

    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        for (String word : dict) {
            for (int i = 0; i < word.length(); i++) {
                String key = word.substring(0, i) + word.substring(i + 1);

                int[] info = new int[] {i, word.charAt(i)};

                List<int[]> list = map.getOrDefault(key, new ArrayList<int[]>());
                list.add(info);

                map.put(key, list);
            }
        }
    }

    /** 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 i = 0; i < word.length(); i++) {
            String key = word.substring(0, i) + word.substring(i + 1);

            if (map.containsKey(key)) {
                for (int[] info : map.get(key)) {
                    if (i == info[0] && word.charAt(i) != info[1]) {
                        return true;
                    }
                }
            }
        }
        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);
 */
```

**(2) Trie**

```java
class MagicDictionary {
    class TrieNode {
        char val;
        boolean isWord;
        TrieNode[] childNode;

        public TrieNode(char val) {
            this.val = val;
            childNode = new TrieNode[26];
        }
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode(' ');
        }

        public void insert(String word) {
            if (word == null || word.length() == 0) {
                return;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (curNode.childNode[index] == null) {
                    curNode.childNode[index] = new TrieNode(c);
                }
                curNode = curNode.childNode[index];
            }
            curNode.isWord = true;
        }

        public boolean search(String word) {
            if (word == null || word.length() == 0) {
                return false;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (curNode.childNode[index] == null) {
                    return false;
                }
                curNode = curNode.childNode[index];
            }
            return curNode.isWord;
        }
    }

    Trie trie;

    /** Initialize your data structure here. */
    public MagicDictionary() {
        trie = new Trie();
    }

    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        for (String word : dict) {
            trie.insert(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) {
        char[] letters = word.toCharArray();
        for (int i = 0; i < word.length(); i++) {
            char oldC = letters[i];

            for (char c = 'a'; c <= 'z'; c++) {
                if (c == oldC) {
                    continue;
                }

                letters[i] = c;
                String newWord = new String(letters);
                if (trie.search(newWord)) {
                    return true;
                }
            }
            letters[i] = oldC;
        }
        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);
 */
```

## 3. Time & Space Complexity

**HashMap**: 时间复杂度O(nm), n为dict里word的数量, m是dict里word的平均长度, 空间复杂度O(nm)

**Trie:** 时间复杂度build: O(nm), n为dict里word的数量, m是dict里word的平均长度, search: O(n \* 25^m), 空间复杂度O(nm)