GeeksforGeeks网格查找字符串问题：我的DFS代码为何无法通过？

问题背景 #

给定n*m的字符二维网格和一个单词，找出网格中该单词的所有出现位置。单词可从任意点出发，沿8个方向（水平左右、垂直上下、4个对角线方向）连续匹配（不可zig-zag）。注意：返回的坐标列表需按字典序排列；若同一坐标出发沿多个方向匹配到单词，列表仅保留一次该坐标。

你实现的DFS代码无法通过测试，问题出在以下几点：

代码问题分析 #

1. 破坏原网格结构：你的DFS中把当前访问的字符改为#再回溯改回，这会导致后续遍历其他起始位置时，原网格的字符被临时修改，影响匹配结果。比如网格中有多个相同字符时，前面的DFS修改会让后面的起始点无法正确匹配。
2. DFS逻辑冗余且有误：因为单词是沿单一方向连续匹配，不需要回溯标记单元格（不会走回头路），修改网格的操作完全没必要，反而会引入bug。

修正后的代码 #

class Solution:
    def searchWord(self, grid, word):
        res = []
        n = len(grid)
        m = len(grid[0]) if n > 0 else 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        
        for i in range(n):
            for j in range(m):
                if grid[i][j] == word[0]:
                    # 遍历所有方向检查是否能匹配完整单词
                    for dr, dc in directions:
                        row, col = i, j
                        match = True
                        for c in word:
                            if row < 0 or row >= n or col < 0 or col >= m or grid[row][col] != c:
                                match = False
                                break
                            row += dr
                            col += dc
                        if match:
                            res.append([i, j])
                            break  # 只要有一个方向匹配，就不再检查其他方向
        
        return sorted(res) if res else []

修正说明 #

• 去掉了修改网格的回溯操作，直接对每个起始点的8个方向逐一检查：沿着当前方向直线走，逐个字符匹配单词。
• 只要某个方向能完整匹配单词，就将该起始坐标加入结果，并且跳出当前方向的循环（避免同一坐标被多次添加）。
• 最后对结果列表按字典序排序，符合题目要求。

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