# Implement Magic Dictionary

<https://leetcode.com/problems/implement-magic-dictionary/description/>

> 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.

## Thoughts

brute-force是对给定的str和dict中的每个string作比较. 想到可以把每个在dict的字符串的每一位删除所形成的新字符串放入一个set中。对给定的字符串依次删除字符，当剩下的字符组成的字符串出现在了set中，即返回true.

但这么做有个问题，即如果给定一个在dict中的字符串时，它也返回true. 所以又创建了一个oriSet记录dict中的字符串，如果给定的match其中一个，直接返回。

可还是有问题，因为即使和oriSet 的match并不意味着给定的string 就是不能通过修改dict中另一个string的某位得来。比如dict中放入\[hello, hallo] 现在给hello, 虽然oriSet包含了hello, 但hello可以由hallo修改一个字符得到. 现在问题变得复杂, 逻辑不大好理清了.

也就是我们要对每个在dict中的每个string在和给定str不同的情况下, 判断是否可以通过删除string和str某字符后match. 但这样又是一一比较, 时间复杂度高.

后来看到大神的解法, 想法其实很接近了, 依然是把所有可能的删除一个字符后形成的substring放入, 不过是放入map中. 然后每个substring维护一个set, 记录下是由谁 **在什么位置上** 放的. 对给定的str, 依然是依次删除一个字符形成新的字符串, 然后和map中匹配, 如果匹配成功再继续遍历sub对应的set, 看是否存在和str不同的放入者.

## Code

```
class MagicDictionary {
    Map<String, Map<Integer, Set<String>>> 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 str : dict) {
            for (int i = 0; i < str.length(); i++) {
                StringBuilder sb = new StringBuilder(str);
                String sub = sb.deleteCharAt(i).toString();
                if (!map.containsKey(sub)) {
                    map.put(sub, new HashMap<>());
                }
                if (!map.get(sub).containsKey(i)) {
                    map.get(sub).put(i, new HashSet<>());
                }
                map.get(sub).get(i).add(str);
            }
        }
    }

    /** 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++) {
            StringBuilder sb = new StringBuilder(word);
            String sub = sb.deleteCharAt(i).toString();
            if (map.containsKey(sub) && map.get(sub).containsKey(i)) {
                if (!map.get(sub).get(i).contains(word) || map.get(sub).get(i).size() > 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);
 */
```

## Analysis

Errors: 1. 如thoughts所说. 2. 位置也很重要, 比如\[ab]和\[ba] 两者删除a后相同, 但对ab只修改一个字符无法变成ba.

search时间复杂度为字符串长度. 空间复杂度为dict长度\*每个string长度.


---

# 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://hao-fu-1.gitbook.io/oj/hash/overlapping/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.