676-实现一个魔法字典(Implement Magic Dictionary)

原文链接: https://leetcode-cn.com/problems/implement-magic-dictionary

英文原文

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.

中文题目

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

实现 MagicDictionary 类：

MagicDictionary() 初始化对象
void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中一个字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

示例：

输入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

提示：

1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] 仅由小写英文字母组成
dictionary 中的所有字符串 互不相同
1 <= searchWord.length <= 100
searchWord 仅由小写英文字母组成
buildDict 仅在 search 之前调用一次
最多调用 100 次 search

通过代码

官方题解

解决方法：

方法一：暴力法

算法：

如果一个字符中只有一个字符可以更改，即它们的汉明距离为 1。
在搜索新单词时，我们只检查长度相同的单词。

[ ]
class MagicDictionary(object):
    def __init__(self):
        self.buckets = collections.defaultdict(list)

    def buildDict(self, words):
        for word in words:
            self.buckets[len(word)].append(word)

    def search(self, word):
        return any(sum(a!=b for a,b in zip(word, candidate)) == 1
                   for candidate in self.buckets[len(word)])

[ ]
class MagicDictionary {
    Map<Integer, ArrayList<String>> buckets;
    public MagicDictionary() {
        buckets = new HashMap();
    }

    public void buildDict(String[] words) {
        for (String word: words) {
            buckets.computeIfAbsent(word.length(), x -> new ArrayList()).add(word);
        }
    }

    public boolean search(String word) {
        if (!buckets.containsKey(word.length())) return false;
        for (String candidate: buckets.get(word.length())) {
            int mismatch = 0;
            for (int i = 0; i < word.length(); ++i) {
                if (word.charAt(i) != candidate.charAt(i)) {
                    if (++mismatch > 1) break;
                }
            }
            if (mismatch == 1) return true;
        }
        return false;
    }
}

复杂度分析

时间复杂度：$O(S)$ 构建和 $O(NK)$ 搜索，其中 $N$ 是魔法字典中的单词数，$S$ 是其中的字母总数，$K$ 是搜索单词的长度。
空间复杂度：$O(S)$。

方法二：广义邻居

回想一下，在方法 1 中，如果一个单词中只有一个字符可以更改以使字符串相等，那么两个单词就是邻居。

让我们假设一个词 “apple” 具有广义邻居 “pple”、“aple”、“aple”、“appe” 和 “appl”。在搜索像 apply 这样的词是否有像 apple 这样的邻居时，我们只需要知道它们是否有一个广义邻居。

算法：
继续上述思考，一个问题是 “apply” 不是自身的邻居，而是具有相同的广义邻居 “pply”。为了解决这个问题，我们将计算生成 “pply” 的源的数量。如果有 2 个或更多，则其中一个不会是 “apply”。如果只有一个，我们应该检查它不是 “apply”。无论是哪种情况，我们都可以确定有一些神奇的单词生成了 “*pply”，而不是 “apply”。

[ ]
class MagicDictionary(object):
    def _genneighbors(self, word):
        for i in xrange(len(word)):
            yield word[:i] + '*' + word[i+1:]

    def buildDict(self, words):
        self.words = set(words)
        self.count = collections.Counter(nei for word in words
                                        for nei in self._genneighbors(word))

    def search(self, word):
        return any(self.count[nei] > 1 or
                   self.count[nei] == 1 and word not in self.words
                   for nei in self._genneighbors(word))

[ ]
public class MagicDictionary {
    Set<String> words;
    Map<String, Integer> count;

    public MagicDictionary() {
        words = new HashSet();
        count = new HashMap();
    }

    private ArrayList<String> generalizedNeighbors(String word) {
        ArrayList<String> ans = new ArrayList();
        char[] ca = word.toCharArray();
        for (int i = 0; i < word.length(); ++i) {
            char letter = ca[i];
            ca[i] = '*';
            String magic = new String(ca);
            ans.add(magic);
            ca[i] = letter;
        }
        return ans;
    }

    public void buildDict(String[] words) {
        for (String word: words) {
            this.words.add(word);
            for (String nei: generalizedNeighbors(word)) {
                count.put(nei, count.getOrDefault(nei, 0) + 1);
            }
        }
    }

    public boolean search(String word) {
        for (String nei: generalizedNeighbors(word)) {
            int c = count.getOrDefault(nei, 0);
            if (c > 1 || c == 1 && !words.contains(word)) return true;
        }
        return false;
    }
}

复杂度分析

时间复杂度：$O(\sum w_i^2)$ 生成和 $O(K^2)$ 搜索，其中 $w_i$ 是 words[i] 的长度，$K$ 是搜索单词的长度。
空间复杂度：$O(\sum w_i^2)$，count 使用的空间。在生成邻居进行搜索时，我们还使用 $O(K^2)$ 空间。

统计信息

通过次数	提交次数	AC比率
7959	13427	59.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
实现 Trie (前缀树)	中等
词典中最长的单词	简单

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途