Medium

题目描述

设计一个使用单词列表进行初始化的数据结构，当给出一个字符串时，你应该能够确定是否可以将字符串中的一个字母改变成为字典中的任何一个字符串。

实现 MagicDictionary 类：

  • MagicDictionary() 初始化对象
  • void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
  • bool search(String searchWord) 给定一个字符串 searchWord，判定能否只将字符串中 一个 字母改变成为字典中的任何一个字符串，如果能则返回 true，否则返回 false

示例 1：

输入
["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

解题思路

这道题要求实现一个魔法字典，能够判断是否可以通过改变搜索词的恰好一个字符来匹配字典中的某个单词。

解题思路：

最直观的方法是哈希表存储 + 暴力匹配。在 buildDict 时将所有单词存储到哈希表中，在 search 时遍历字典中的每个单词，检查是否恰好有一个字符不同。

具体实现步骤：

  1. 使用哈希表按长度分组存储字典中的单词，这样可以快速过滤掉长度不同的单词
  2. 在搜索时，只需要检查与搜索词长度相同的单词
  3. 对于每个候选单词，统计不同字符的个数，如果恰好为1，则返回true

更高效的解法是使用字典树（Trie），但考虑到题目的数据规模较小（字典长度≤100，每次最多调用100次search），简单的哈希表方法已经足够高效且更容易理解。

推荐解法： 哈希表按长度分组 + 逐字符比较，时间复杂度低且实现简单。

代码实现

class MagicDictionary {
private:
    unordered_map<int, vector<string>> dict;
    
public:
    MagicDictionary() {
        
    }
    
    void buildDict(vector<string> dictionary) {
        dict.clear();
        for (const string& word : dictionary) {
            dict[word.length()].push_back(word);
        }
    }
    
    bool search(string searchWord) {
        int len = searchWord.length();
        if (dict.find(len) == dict.end()) {
            return false;
        }
        
        for (const string& word : dict[len]) {
            int diff = 0;
            for (int i = 0; i < len; i++) {
                if (word[i] != searchWord[i]) {
                    diff++;
                    if (diff > 1) break;
                }
            }
            if (diff == 1) {
                return true;
            }
        }
        return false;
    }
};

class MagicDictionary:

    def __init__(self):
        self.dict = {}

    def buildDict(self, dictionary: List[str]) -> None:
        self.dict.clear()
        for word in dictionary:
            length = len(word)
            if length not in self.dict:
                self.dict[length] = []
            self.dict[length].append(word)

    def search(self, searchWord: str) -> bool:
        length = len(searchWord)
        if length not in self.dict:
            return False
        
        for word in self.dict[length]:
            diff = 0
            for i in range(length):
                if word[i] != searchWord[i]:
                    diff += 1
                    if diff > 1:
                        break
            if diff == 1:
                return True
        return False

public class MagicDictionary {
    private Dictionary<int, List<string>> dict;

    public MagicDictionary() {
        dict = new Dictionary<int, List<string>>();
    }
    
    public void BuildDict(string[] dictionary) {
        dict.Clear();
        foreach (string word in dictionary) {
            int length = word.Length;
            if (!dict.ContainsKey(length)) {
                dict[length] = new List<string>();
            }
            dict[length].Add(word);
        }
    }
    
    public bool Search(string searchWord) {
        int length = searchWord.Length;
        if (!dict.ContainsKey(length)) {
            return false;
        }
        
        foreach (string word in dict[length]) {
            int diff = 0;
            for (int i = 0; i < length; i++) {
                if (word[i] != searchWord[i]) {
                    diff++;
                    if (diff > 1) break;
                }
            }
            if (diff == 1) {
                return true;
            }
        }
        return false;
    }
}

var MagicDictionary = function() {
    this.dictionary = [];
};

/** 
 * @param {string[]} dictionary
 * @return {void}
 */
MagicDictionary.prototype.buildDict = function(dictionary) {
    this.dictionary = dictionary;
};

/** 
 * @param {string} searchWord
 * @return {boolean}
 */
MagicDictionary.prototype.search = function(searchWord) {
    for (let word of this.dictionary) {
        if (word.length === searchWord.length) {
            let diffCount = 0;
            for (let i = 0; i < word.length; i++) {
                if (word[i] !== searchWord[i]) {
                    diffCount++;
                    if (diffCount > 1) break;
                }
            }
            if (diffCount === 1) return true;
        }
    }
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
buildDictO(n)O(n)
searchO(m × k)O(1)

其中 n 是字典中所有单词的总字符数，m 是与搜索词长度相同的单词数量，k 是单词长度。

相关题目