发表于 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)

• LC 题目链接