原文链接: https://leetcode-cn.com/problems/US1pGT

中文题目

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

实现 MagicDictionary 类：

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

 

示例：

输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["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

 

注意：本题与主站 676 题相同： https://leetcode-cn.com/problems/implement-magic-dictionary/

通过代码

高赞题解

前缀树

此类问题若是使用哈希表并不能很好得解决，合适的方法应该是使用前缀树，然后在前缀树中查找只修改一个字符的字符串。前缀的实现和前几题类似，如下

// 构造前缀树节点
class Trie {
public:
    bool isWord;
    vector<Trie*> children;
    Trie () : isWord(false), children(26, nullptr) {}

    void insert(const string& str) {
        Trie* node = this;
        for (auto& ch : str) {
            if (node->children[ch - 'a'] == nullptr) {
                node->children[ch - 'a'] = new Trie();
            }
            node = node->children[ch - 'a'];
        }
        node->isWord = true;
    }
};

接下来分析如何在前缀树中查找只修改一个字符的字符串，可以根据 dfs 搜索前缀树的每条路径。如果到达的节点与字符串中的字符不匹配，则表示此时需要修改该字符以匹配路径。如果到达对应字符串的最后一个字符所对应的节点，且该节点的 isWord 为 ture，并且当前路径刚好修改了字符串中的一个字符，那么就找到了符合要求的路径，返回 true。完整代码如下：

// 构造前缀树节点
class Trie {
public:
    bool isWord;
    vector<Trie*> children;
    Trie () : isWord(false), children(26, nullptr) {}

    void insert(const string& str) {
        Trie* node = this;
        for (auto& ch : str) {
            if (node->children[ch - 'a'] == nullptr) {
                node->children[ch - 'a'] = new Trie();
            }
            node = node->children[ch - 'a'];
        }
        node->isWord = true;
    }
};


class MagicDictionary {
private:
    Trie* root;
    bool dfs(Trie* root, string& word, int i, int edit) {
        if (root == nullptr) {
            return false;
        }

        if (root->isWord && i == word.size() && edit == 1) {
            return true;
        }

        if (i < word.size() && edit <= 1) {
            bool found = false;
            for (int j = 0; j < 26 && !found; ++j) {
                int next = (j == word[i] - 'a') ? edit : edit + 1;
                found = dfs(root->children[j], word, i + 1, next);
            }

            return found;
        }

        return false;
    }

public:
    /** Initialize your data structure here. */
    MagicDictionary() {
        root = new Trie();
    }
    
    void buildDict(vector<string> dictionary) {
        for (auto& word : dictionary) {
            root->insert(word);
        }
    }
    
    bool search(string searchWord) {
        return dfs(root, searchWord, 0, 0);
    }
};

统计信息

通过次数	提交次数	AC比率
2026	3251	62.3%

提交历史

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