实现一个魔法字典 图解题解

这道题到底在问什么

输入

buildDict(["hello","world","leetcode"]) search("hhllo")

输出

true（hhllo 把第 2 位 h 改成 e 就成 hello）

输入

search("hello")

输出

false（它本身就在字典里，0 处改动；本题要求恰好改 1 处）

最优解：一步一步想明白

1. 3核心就一个计数：逐位比较，数不同的位数 diff。diff==1 即命中。下面把每一位的比较演给你看。
2. 4【查询 "hhllo" · 候选 1/2】格子里是候选词「world」，要和查询词「hhllo」一位一位比。diff 记录目前为止有几位不同，从 0 开始。
3. 5指针走到第 0 位。查询词这位是 'h'，候选这位是 'w'，两者不同，diff 要加一。
4. 6这位不同，diff 加一变成 1（红色是不同的位）。继续比下一位。
5. 7指针走到第 1 位。查询词这位是 'h'，候选这位是 'o'，两者不同，diff 要加一。
6. 8这位不同，diff 加一变成 2（红色是不同的位）。继续比下一位。
7. 9指针走到第 2 位。查询词这位是 'l'，候选这位是 'r'，两者不同，diff 要加一。
8. 10这位不同，diff 加一变成 3（红色是不同的位）。继续比下一位。
9. 11指针走到第 3 位。查询词这位是 'l'，候选这位是 'l'，两者相同，diff 不变。
10. 12这位相同，diff 保持 3（绿色是到目前为止相同的位）。继续比下一位。
11. 13指针走到第 4 位。查询词这位是 'o'，候选这位是 'd'，两者不同，diff 要加一。
12. 14这位不同，diff 加一变成 4（红色是不同的位）。继续比下一位。
13. 15比完整词，一共 4 位不同。diff 不等于 1，改一处变不成「world」，换下一个候选继续试。
14. 16【查询 "hhllo" · 候选 2/2】格子里是候选词「hello」，要和查询词「hhllo」一位一位比。diff 记录目前为止有几位不同，从 0 开始。
15. 17指针走到第 0 位。查询词这位是 'h'，候选这位是 'h'，两者相同，diff 不变。
16. 18这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
17. 19指针走到第 1 位。查询词这位是 'h'，候选这位是 'e'，两者不同，diff 要加一。
18. 20这位不同，diff 加一变成 1（红色是不同的位）。继续比下一位。
19. 21指针走到第 2 位。查询词这位是 'l'，候选这位是 'l'，两者相同，diff 不变。
20. 22这位相同，diff 保持 1（绿色是到目前为止相同的位）。继续比下一位。
21. 23指针走到第 3 位。查询词这位是 'l'，候选这位是 'l'，两者相同，diff 不变。
22. 24这位相同，diff 保持 1（绿色是到目前为止相同的位）。继续比下一位。
23. 25指针走到第 4 位。查询词这位是 'o'，候选这位是 'o'，两者相同，diff 不变。
24. 26这位相同，diff 保持 1（绿色是到目前为止相同的位）。继续比下一位。
25. 27比完整词，一共 1 位不同。diff 恰好等于 1，说明只改那一个红色位置就能变成「hello」——命中，search 返回 true。
26. 28【查询 "world" · 候选 1/2】格子里是候选词「hello」，要和查询词「world」一位一位比。diff 记录目前为止有几位不同，从 0 开始。
27. 29指针走到第 0 位。查询词这位是 'w'，候选这位是 'h'，两者不同，diff 要加一。
28. 30这位不同，diff 加一变成 1（红色是不同的位）。继续比下一位。
29. 31指针走到第 1 位。查询词这位是 'o'，候选这位是 'e'，两者不同，diff 要加一。
30. 32这位不同，diff 加一变成 2（红色是不同的位）。继续比下一位。
31. 33指针走到第 2 位。查询词这位是 'r'，候选这位是 'l'，两者不同，diff 要加一。
32. 34这位不同，diff 加一变成 3（红色是不同的位）。继续比下一位。
33. 35指针走到第 3 位。查询词这位是 'l'，候选这位是 'l'，两者相同，diff 不变。
34. 36这位相同，diff 保持 3（绿色是到目前为止相同的位）。继续比下一位。
35. 37指针走到第 4 位。查询词这位是 'd'，候选这位是 'o'，两者不同，diff 要加一。
36. 38这位不同，diff 加一变成 4（红色是不同的位）。继续比下一位。
37. 39比完整词，一共 4 位不同。diff 不等于 1，改一处变不成「hello」，换下一个候选继续试。
38. 40【查询 "world" · 候选 2/2】格子里是候选词「world」，要和查询词「world」一位一位比。diff 记录目前为止有几位不同，从 0 开始。
39. 41指针走到第 0 位。查询词这位是 'w'，候选这位是 'w'，两者相同，diff 不变。
40. 42这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
41. 43指针走到第 1 位。查询词这位是 'o'，候选这位是 'o'，两者相同，diff 不变。
42. 44这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
43. 45指针走到第 2 位。查询词这位是 'r'，候选这位是 'r'，两者相同，diff 不变。
44. 46这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
45. 47指针走到第 3 位。查询词这位是 'l'，候选这位是 'l'，两者相同，diff 不变。
46. 48这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
47. 49指针走到第 4 位。查询词这位是 'd'，候选这位是 'd'，两者相同，diff 不变。
48. 50这位相同，diff 保持 0（绿色是到目前为止相同的位）。继续比下一位。
49. 51比完整词，一共 0 位不同。diff 不等于 1，改一处变不成「world」，换下一个候选继续试。
50. 52查询 "world" 时：和 hello 比 diff=4，和它自己比 diff=0（全绿、一处没改）。没有任何候选的 diff 等于 1，所以恰好改一处变不出新词，返回 false。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class MagicDictionary:
    def buildDict(self, words):
        self.words = words            # 存下所有单词
    def search(self, word):
        for w in self.words:
            if len(w) != len(word):   # 只比等长的
                continue
            diff = sum(a != b for a, b in zip(word, w))
            if diff == 1:             # 恰好改一处
                return True
        return False

class MagicDictionary {
    vector<string> ws;
public:
    void buildDict(vector<string> words){ ws = words; }
    bool search(string word){
        for (auto& w : ws) {
            if (w.size() != word.size()) continue;
            int diff = 0;
            for (int i=0;i<w.size();i++) diff += w[i]!=word[i];
            if (diff == 1) return true;
        }
        return false;
    }
};

class MagicDictionary {
    String[] ws;
    public void buildDict(String[] words){ ws = words; }
    public boolean search(String word){
        for (String w : ws) {
            if (w.length() != word.length()) continue;
            int diff = 0;
            for (int i=0;i<w.length();i++)
                if (w.charAt(i) != word.charAt(i)) diff++;
            if (diff == 1) return true;
        }
        return false;
    }
}

复杂度

面试官可能追问