JZX轻语：简
LeetCode 676 - 实现一个魔法字典
发表于2024年04月09日
该题目有两种做法：第一种使用一个字典维护下单词长度 -> 单词列表信息，搜索的时候取相同长度的单词列表，依次比对是否存在差一个字母的单词；
第二种则是Trie树的经典做法，使用Trie维护所有的单词信息，然后搜索的时候使用DFS递归，如果当前字母没有相应的节点可以递归，则使用一个布尔变量modified标记该搜索发生了一次字母变更，并改为向兄弟节点继续遍历。如果第二次遇到没有可递归的情况（modified已经为True），则搜索失败。如果最终找到对应的节点，则需要判断该节点是否对应一个完整的单词，且modified的值为True。
方法1使用字典+遍历的做法：
from collections import defaultdict
class MagicDictionary:
def __init__(self):
self._lenToWord = defaultdict(list) # type: defaultdict[int, list]
def buildDict(self, dictionary: List[str]) -> None:
for word in dictionary:
self._lenToWord[len(word)].append(word)
def search(self, searchWord: str) -> bool:
for word in self._lenToWord[len(searchWord)]:
diffCnt = 0
for i, c1 in enumerate(searchWord):
c2 = word[i]
if c1 != c2:
diffCnt += 1
if diffCnt > 1: # early break
break
if diffCnt == 1:
return True
return False方法2使用Trie的做法：
class Trie:
def __init__(self):
self.children = {}
self.is_finished = False # 该节点是否对应一个完整的单词
class MagicDictionary:
def __init__(self):
self._root = Trie()
def buildDict(self, dictionary: List[str]) -> None:
# 构建trie
for word in dictionary:
cur_node = self._root
for ch in word:
if ch not in cur_node.children:
cur_node.children[ch] = Trie()
cur_node = cur_node.children[ch]
cur_node.is_finished = True
def search(self, searchWord: str) -> bool:
def dfs(cur_node: Trie, pos: int, modified: bool):
nonlocal searchWord
if pos == len(searchWord):
# 单词已经遍历完毕, 判断最后遍历的节点是否对应一个完整的单词, 且有发生过更改
return cur_node.is_finished and modified
# 当前位置能匹配上, 继续递归
if searchWord[pos] in cur_node.children:
if dfs(cur_node.children[searchWord[pos]], pos + 1, modified):
return True
# 否则, 如果搜索过程没有发生过修改, 则对此位置进行单词变换, 换兄弟节点继续下去
if not modified:
for ch, child in cur_node.children.items():
if ch != searchWord[pos] and dfs(child, pos + 1, True):
return True
# 已经发生过修改 or 换了兄弟节点也不行, 搜索失败
return False
return dfs(self._root, 0, False)