递归回溯实现二维数组单词搜索：LeetCode测试用例报错排查

我在LeetCode上解决单词搜索问题时，遇到两个测试用例报错：

• board = [["a","a"]], word = "aa"
• board = [["a"]], word = "a"

但相同代码在Google Colab中运行这两个用例均正常，怀疑是Python版本差异导致，但不清楚具体问题，求帮忙定位原因。

代码如下： #

from typing import List

class Solution:
    def exist2(self, board: List[List[str]], word: str, current_row, current_col,\
              match_index=0,seen_cells=[]) -> bool:
        if match_index==len(word):
            return True
        else:                
            for i in range(-1,2):
                for j in range(-1,2):
                    if current_row+i>=0 and current_col+j>=0 and current_row+i<len(board)\
                    and current_col+j<len(board[0]) and\
                    board[current_row+i][current_col+j]==word[match_index] and\
                    (current_row+i,current_col+j) not in seen_cells\
                    and i+j!=-2 and i+j!=2:

                        match_index+=1
                        seen_cells.append((current_row+i,current_col+j))
                        
                        if self.exist2(board, word, current_row+i, current_col+j,\
                        match_index,seen_cells):
                            return True
                        else:
                            seen_cells.remove((current_row+i,current_col+j))
                            current_row,current_col=seen_cells[-1]                            
            return False

    def exist(self, board: List[List[str]], word: str, current_row=0, current_col=0,\
              match_index=0,seen_cells=[]) -> bool:
        start_index=[]       
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j]==word[0]:
                    start_index.append((i,j))
        for ele in start_index:
            if self.exist2(board, word, ele[0],ele[1]):
                return True
        return False

def main():
    sol = Solution()
    print(sol.exist([["a","a"]],'a'))

问题定位与修复： #

核心问题和Python版本无关，是可变默认参数的陷阱加上代码逻辑错误导致：

1. 可变默认参数复用问题：
   exist2和exist函数都用seen_cells=[]作为默认参数。Python中，可变默认参数在函数定义时就会创建固定列表对象，每次调用如果不传该参数，会复用同一个列表。LeetCode会多次调用函数测试不同用例，前一次的seen_cells状态会残留到下一次，导致判断错误。而Colab中单次运行不会触发这个问题。

2. 回溯逻辑错误：
   exist2中的current_row,current_col=seen_cells[-1]完全错误，递归调用已经通过参数传递了当前位置，回溯时不需要修改这两个变量，这行代码会导致位置跳转混乱，破坏搜索逻辑。

3. 语法与调用错误：
   原main函数缺少冒号，且未实例化Solution对象就调用exist方法，属于基础语法错误。

修复后的代码： #

from typing import List

class Solution:
    def exist2(self, board: List[List[str]], word: str, current_row, current_col,
              match_index=0, seen_cells=None) -> bool:
        # 初始化空列表，避免可变默认参数复用
        if seen_cells is None:
            seen_cells = []
        if match_index == len(word):
            return True
        
        # 仅遍历上下左右四个合法方向（符合题目要求）
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        for dx, dy in directions:
            new_row = current_row + dx
            new_col = current_col + dy
            if (0 <= new_row < len(board) and
                0 <= new_col < len(board[0]) and
                board[new_row][new_col] == word[match_index] and
                (new_row, new_col) not in seen_cells):
                
                seen_cells.append((new_row, new_col))
                if self.exist2(board, word, new_row, new_col, match_index + 1, seen_cells):
                    return True
                # 回溯：移除当前单元格
                seen_cells.pop()
        return False

    def exist(self, board: List[List[str]], word: str) -> bool:
        # 遍历所有起始位置
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    # 每个起始位置初始化新的已访问列表
                    if self.exist2(board, word, i, j, 1, [(i,j)]):
                        return True
        return False

def main():
    sol = Solution()
    print(sol.exist([["a","a"]], "aa"))  # 输出True
    print(sol.exist([["a"]], "a"))       # 输出True

if __name__ == "__main__":
    main()

额外说明：原代码的双重循环遍历了8个方向（包括对角线），但单词搜索题目要求只能走上下左右四个相邻单元格，修复时一并修正了这个逻辑，确保符合题目要求。

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