【算法】实现一个魔法字典

作者：lomtom 个人网站：lomtom.cn 你的支持就是我最大的动力。

题目难度：中等[1]

题目描述：

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

解题分析及思路：

Hash + 枚举

本题的重点在于如何构建一个适合search的MagicDictionary结构，并且在search时怎么搜索才能符合条件。

可以将字典 dictionary的放入到数组内，然后每次search时，可以遍历整个数组，当长度相等时，并且两个字符串只有一个字母不相同时，返回true。

为了优化比较的次数，可以将字典 dictionary的元素按照长度放在一个map中，每次只要比较相同长度的值即可。

那么怎么判断两个字符串只有一个字母不相同呢？

可以两个字符串的每一个字符比较，并且计算两个字符串不相同的字母的个数，如果只有一个时，则满足题目中的条件，返回true即可。遍历完，还没有找到符合条件的字符串，返回false。

代码分析：

定义MagicDictionary结构体，包含一个属性m，是一个key为int（长度），value为[]string的map。

type MagicDictionary struct {
 m map[int][]string
}

func Constructor() MagicDictionary {
 return MagicDictionary{
  make(map[int][]string),
 }
}

构建MagicDictionary结构体，将dictionary中的元素按照自身长度放入map中，方便后续搜索。

func (this *MagicDictionary) BuildDict(dictionary []string) {
 for index := range dictionary {
  this.m[len(dictionary[index])] = append(this.m[len(dictionary[index])], dictionary[index])
 }
}

search函数，先从map中查找是否有相同长度l的值，如果没有返回false，有的话继续遍历this.m[l]所对应的值。

遍历每一个元素时，对比每一个字母，并且统计不同字母的个数，统计完一个字符串时，判断不同字母个数是否符合条件即可。

func (this *MagicDictionary) Search(searchWord string) bool {
 l := len(searchWord)
 if values, ok := this.m[l]; ok {
  for _, value := range values {
   var count int
   for index := 0; index < l; index++ {
    if value[index] != searchWord[index] {
     count++
    }
   }
   if count == 1 {
    return true
   }
  }
 }
 return false
}

最后代码：实现一个魔法字典[2]

复杂度：

• 时间复杂度：O(nl)，其中 n 是数组 dictionary 的长度，l 是数组 dictionary 中字符串的平均长度，q 是函数 search(searchWord) 的调用次数
• 空间复杂度：O(n)，数组所需空间

执行结果：

• 执行用时：8 ms, 在所有 Go 提交中击败了100.00%的用户
• 内存消耗：6.8 MB, 在所有 Go 提交中击败了74.42%的用户

引用

[1]

leetcode: https://leetcode.cn/problems/implement-magic-dictionary/

[2]

code: https://github.com/lomtom/algorithm-go/blob/main/leetcode/676/676实现一个魔法字典_test.g