递归回溯 - 二维数组中的单词搜索

Question

我正在尝试 leetcode 上的单词搜索问题这里。 Leetcode 似乎给我两个测试用例的错误：

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

和：

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

但是对于这两个测试用例，以下代码似乎在 Google colab 上运行良好。有人可以查明具体原因吗？这很可能是 Python 版本差异的结果。但对我来说到底是什么损失啊！预先感谢！

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()
    print(exist([["a","a"]],'a'))

Answer 1

您的代码存在多个问题。

首先，您依赖于

seen_cells

的默认参数，但该列表只有一个实例，用于对

exist2

的所有调用。多个测试用例将共享相同的状态，当

seen_cells

中存在之前调用

exist2

的元组时，这会导致问题。

您还在

match_index

中内部循环的每次迭代中递增

exist2

，即使每次迭代应该是独立的。您应该将

match_index + 1

传递给

exist2

的递归调用。

此外，您仅通过选中

i+j!=-2 and i+j!=2

即可允许对角线移动。例如，由于

-1 + 1 = 0

既不等于

-2

也不等于

2

，因此允许移动 (-1, 1)。检查

i

和

j

之一是否非零是正确的。这可以通过

((not i) ^ (not j))

简洁地完成，不过您也可以更明确地写出来。

此外，您不要将路径中的第一个单元格添加到

seen_paths

。您可以通过在

exist2

开头检查匹配项并在返回之前从

seen_cells

中删除来修复此差一错误。请注意，

current_row,current_col=seen_cells[-1]

行没有多大意义，可能会导致

IndexError

；删除它。

最后，这个解决方案太慢了，因为检查列表中是否存在是一个线性时间操作。相反，使用

set

或布尔矩阵来标记哪些单元格已经通过。