实现一个魔法字典

2024-08-12

leetcode

题目：

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

实现 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

思路：

对于本题来说，我们有两种做法：第一种是把字典中的所有字符串存储在数组中，而当进行 search 操作时，我们将待查询的字符串和数组中的字符串依次进行比较；第二种是提前把字典中每个字符串替换任一字母的结果存在哈希表中，当进行 search 操作时，我们只需要检查待查询的字符串本身是否在哈希表中即可。

记字典中字符串的个数为 n，平均长度为 l，查询的次数为 q，字符集为 Σ。那么：

第一种方法需要 O(nl) 的时间把所有字符串存储在数组中，每一次查询也需要 O(nl) 的时间，总时间复杂度为 O(nl + qnl) = O(qnl)；

第二种方法需要 O(nl^2∣Σ∣) 的时间把所有字符串替换任一字母的结果存在哈希表中，每一次查询仅需要 O(l) 的时间，总时间复杂度为 O(nl^2∣Σ∣ + ql)。

在本题的数据范围中 n,l,q ≤ 100 同阶，而 ∣Σ∣ = 26，因此第一种方法的时间复杂度较低，下面的代码使用的是第一种方法。

代码：

class MagicDictionary {
public:
    vector<string> words;
    MagicDictionary() {

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

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dictionary);
 * bool param_2 = obj->search(searchWord);
 */

字典树优化枚举

思路：

我们也可以使用字典树代替数组，将所有字符串进行存储。这一部分需要的时间是相同的。

在查询时，我们可以使用递归 + 回溯的方法，使用递归函数 dfs(node, pos, modified)，其中的变量分别表示：当前遍历到的字典树上的节点是 node 以及待查询字符串 searchWord 的第 pos 个字符，并且在之前的遍历中是否已经替换过恰好一个字符（如果替换过，那么 modified 为 true，否则为 false）。

如果 node 有一个值为 searchWord[pos] 的子节点，那么我们就可以继续进行递归。同时，如果 modified 为 false，我们可以将 searchWord[pos] 替换成任意一个是 node 子节点的字符，将 modified 置为 true 并继续进行递归。

当 pos 等于 searchWord 的长度时，说明递归完成。此时我们需要检查 node 是否是一个字典树上的结束节点（即一个单词的末尾），同时需要保证 modified 为 true，因为我们必须进行一次修改。

代码：

struct Trie {
    bool is_finished;
    Trie* child[26];

    Trie() {
        is_finished = false;
        fill(begin(child), end(child), nullptr);
    }
};

class MagicDictionary {
public:
    MagicDictionary() {
        root = new Trie();
    }
    
    void buildDict(vector<string> dictionary) {
        for (auto&& word: dictionary) {
            Trie* cur = root;
            for (char ch: word) {
                int idx = ch - 'a';
                if (!cur->child[idx]) {
                    cur->child[idx] = new Trie();
                }
                cur = cur->child[idx];
            }
            cur->is_finished = true;
        }
    }
    
    bool search(string searchWord) {
        function<bool(Trie*, int, bool)> dfs = [&](Trie* node, int pos, bool modified) {
            if (pos == searchWord.size()) {
                return modified && node->is_finished;
            }
            int idx = searchWord[pos] - 'a';
            if (node->child[idx]) {
                if (dfs(node->child[idx], pos + 1, modified)) {
                    return true;
                }
            }
            if (!modified) {
                for (int i = 0; i < 26; ++i) {
                    if (i != idx && node->child[i]) {
                        if (dfs(node->child[i], pos + 1, true)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        };

        return dfs(root, 0, false);
    }

private:
    Trie* root;
};