LeetCode单词搜索问题：为何采用回溯而非常规DFS？

嘿，这个问题问得特别到位！其实你猜的方向完全没错——回溯本质上就是带「状态重置」的DFS，咱们来把这层关系拆解清楚，你就能明白为什么在这个问题里回溯（或者说带状态管理的DFS）是最合理的选择了。

先理清楚核心概念：常规DFS vs 回溯 #

• 常规DFS一般用于遍历所有可达节点（比如找图的连通分量），这类场景里每个节点只需要访问一次，不需要撤销访问标记，走到底就行。
• 但在Word Search问题中，我们需要尝试不同的路径组合：比如从某个单元格出发，往右走没找到目标单词，就得退回来，再尝试往下走。这时候必须把之前标记为「已访问」的单元格重新设为「未访问」——这就是回溯的核心：尝试路径→失败→回滚状态→再尝试其他路径。

关于visited矩阵：它本身就是回溯的实现方式！ #

你提到的用visited矩阵替代的思路完全可行，但这其实就是回溯的一种写法啊！举个代码例子你就能明白：

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False]*cols for _ in range(rows)]
    
    def backtrack(i, j, current_idx):
        # 找到完整单词，直接返回成功
        if current_idx == len(word):
            return True
        # 越界、已访问、字符不匹配，直接返回失败
        if i < 0 or i >= rows or j <0 or j >= cols or visited[i][j] or board[i][j] != word[current_idx]:
            return False
        
        # 标记当前单元格为已访问（进入分支前的状态变更）
        visited[i][j] = True
        # 尝试四个方向的路径
        found = backtrack(i+1,j,current_idx+1) or backtrack(i-1,j,current_idx+1) or backtrack(i,j+1,current_idx+1) or backtrack(i,j-1,current_idx+1)
        # 回溯：撤销标记（退出分支后重置状态）
        visited[i][j] = False
        
        return found
    
    # 遍历所有单元格作为起始点
    for i in range(rows):
        for j in range(cols):
            if backtrack(i,j,0):
                return True
    return False

这里的visited[i][j] = False就是典型的回溯操作——如果当前路径走不通，就得把状态改回去，让其他可能的路径还能使用这个单元格。要是只做DFS不回溯，一旦标记了某个单元格为已访问，后续所有路径都用不了它，肯定会漏掉正确的解。

额外小技巧：不用visited矩阵也能回溯 #

甚至可以不用单独的visited矩阵，直接修改原board的字符（比如把当前单元格改成#这种特殊字符），回溯的时候再改回原字符，这样能节省额外的空间，本质还是回溯的思路。

总结 #

你说的「常规DFS」是没有状态回滚的DFS，在这个问题里根本行不通——因为我们需要探索多条独立的路径，每条路径的访问状态不能互相干扰。而用visited矩阵的方式，本质就是带状态回溯的DFS，这正是解决这类路径探索问题的标准姿势。两者不是对立的，回溯是DFS针对「需要尝试多种路径、必须回滚状态」场景的特殊应用~

内容的提问来源于stack exchange，提问作者J. Doe