LeetCode 127. Word Ladder DFS解法错误排查：为何无法通过测试？

解决方案思路 #

• isDiff1函数：判断两个单词是否仅相差一个字符
• 构建邻接表：将所有仅差一个字符的单词连接，形成图结构
• 预处理wordList：若beginWord不在列表中，则将其加入
• DFS遍历实现：定义dfs(w)函数，查找从单词w到endWord的最短路径
• 缓存优化：使用缓存存储已计算的路径长度，避免重复计算

该解法通过了50个测试用例中的33个，但在第34个用例上出错。我清楚邻接表生成方式（O(n²*len(w))）和DFS查找最短路径的效率问题，但无法定位代码逻辑中的错误点。

代码实现 #

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0

        def isDiff1(w1,w2):
            counter = 0
            for i in range(len(w1)):
                if w1[i] != w2[i]:
                    counter += 1
            return True if counter <= 1 else False
        if beginWord not in wordList:
            wordList.append(beginWord)
        # O(n)
        adjList = { word:[] for word in wordList }
        # O(n^2*len(w))
        for w1 in adjList:
            for w2 in wordList:
                if w1 == w2:
                    continue
                if isDiff1(w1,w2):
                    adjList[w1].append(w2)
        
        # dfs returns the minimum num of steps to reach endWord from w
        # if it cannot reach endWord, it returns 0
        vis = set()
        cache = {}
        def dfs(w):
            if w == endWord:
                return 1
            if w in vis:
                return 0
            if w in cache:
                return cache[w]
            
            canReach = False
            minSteps = float('inf')
            vis.add(w)
            for neighbor in adjList[w]:
                temp = dfs(neighbor)
                if temp:
                    canReach = True
                    minSteps = min(minSteps,temp)
            vis.remove(w)
            cache[w] = minSteps+1 if canReach else 0
            return cache[w]
        
        return dfs(beginWord)

内容的提问来源于stack exchange，提问作者adam tan