LeetCode 79单词搜索测试案例存疑，代码未通过且逻辑困惑

测试案例为何返回true #

给定矩阵：

[["C","A","A"],
 ["A","A","A"],
 ["B","C","D"]]

目标单词"AAB"存在合法路径，比如：

• 第一步取(1,1)位置的'A'（矩阵中间的A）
• 第二步取(1,0)位置的'A'（左邻，水平相邻）
• 第三步取(2,0)位置的'B'（下邻，垂直相邻）
  这条路径完全符合水平/垂直相邻、不重复使用单元格的要求，因此该测试案例应返回true。

代码问题分析与修复 #

你的代码存在两个核心问题：

1. 回溯时未恢复原字符：递归搜索时将当前单元格设为'.'标记已访问，但如果当前路径搜索失败，没有把字符还原，导致后续其他搜索路径无法使用该单元格，这是测试案例失败的关键原因。
2. 冗余判断：if len(word) == 1 and board[r][c] == word: 是多余的，因为第一个判断条件已经验证了board[r][c] == word[0]，当len(word) == 1时，word[0]等价于word，无需重复判断。

修正后的代码如下：

from typing import List

def exist(self, board: List[List[str]], word: str) -> bool:
    M, N = len(board), len(board[0])
    
    def search(r, c, word_idx):
        # 边界或字符不匹配，返回False
        if r < 0 or r >= M or c < 0 or c >= N or board[r][c] != word[word_idx]:
            return False
        # 已经匹配到最后一个字符，返回True
        if word_idx == len(word) - 1:
            return True
        # 标记当前单元格为已访问
        temp = board[r][c]
        board[r][c] = '.'
        # 搜索四个方向
        found = search(r+1, c, word_idx+1) or search(r-1, c, word_idx+1) or \
                search(r, c+1, word_idx+1) or search(r, c-1, word_idx+1)
        # 回溯，恢复原字符
        board[r][c] = temp
        return found
    
    for r in range(M):
        for c in range(N):
            if search(r, c, 0):
                return True
    return False

额外优化：用word_idx代替每次切片word[1:]，减少字符串拷贝开销，提升运行效率。

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