LeetCode 211：添加与搜索单词数据结构实现错误排查求助

原代码核心错误 #

你的代码在处理通配符.时采用了扁平化合并子节点字典的方式，这会丢失字典树的层级路径信息，导致部分复杂分支场景下匹配逻辑错误。具体来说：

• 遇到.时，你将当前节点所有子节点的键值对合并为一个新字典，这相当于直接跳到了子节点的下一层，而非保留当前所有可能的子节点路径继续匹配剩余字符串。
• 当多个子节点存在相同键时，合并字典会发生键覆盖，丢失部分路径的匹配可能性。

修复方案：递归DFS实现多路径匹配 #

正确的做法是使用深度优先搜索（DFS），遇到通配符时遍历当前节点的所有子节点，对每个子节点递归检查剩余字符串是否匹配，只要有一条路径匹配成功就返回True。

修复后的完整代码：

class WordDictionary(object):

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

    def addWord(self, word):
        """
        :type word: str
        :rtype: None
        """
        current = self.map
        for c in word:
            if c not in current:
                current[c] = {}
            current = current[c]
        current['end'] = True  # 用布尔值标记单词结束，更简洁高效

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        def dfs(node, index):
            # 已遍历完所有字符，检查当前节点是否是单词结尾
            if index == len(word):
                return 'end' in node
            
            char = word[index]
            if char == '.':
                # 遍历所有子节点，递归检查剩余字符串
                for child_node in node.values():
                    if dfs(child_node, index + 1):
                        return True
                return False
            else:
                # 当前字符不在子节点中，直接返回False
                if char not in node:
                    return False
                # 递归进入子节点，继续匹配下一个字符
                return dfs(node[char], index + 1)
        
        return dfs(self.map, 0)

关键修改说明 #

1. 单词结束标记优化：将current['end'] = {}改为current['end'] = True，既节省空间又语义更明确。
2. DFS递归匹配：
   • 递归函数dfs接收当前节点和当前匹配的字符索引，逐层检查。
   • 遇到通配符.时，遍历当前节点的所有子节点，对每个子节点递归匹配剩余字符，确保所有可能的路径都被检查。
   • 普通字符则直接进入对应子节点继续匹配，不存在则返回False。

这种方式能正确处理所有分支场景，包括多个通配符、复杂路径匹配等情况，解决原代码的逻辑错误。

内容的提问来源于stack exchange，提问作者Kanchon Gharami