DFS 中问题：在网格中查找字符串，我的代码出了什么问题？

Question

我陷入了一个 Geekforgeeks 问题（https://practice.geeksforgeeks.org/problems/find-the-string-in-grid0111/1）

说明在这里：在网格中查找字符串

给定一个由 n*m 个字符和一个单词组成的 2D 网格，找到给定单词在网格中的所有出现位置。一个单词可以在任意点的所有 8 个方向上进行匹配。如果所有字符都在某个方向上匹配（不是锯齿形形式），则称单词是在该方向上找到的。 8 个方向是水平向左、水平向右、垂直向上、垂直向下和 4 个对角方向。

注意：返回的列表应该是按字典顺序最小的。如果可以从同一坐标开始在多个方向上找到该单词，则列表应仅包含该坐标一次。

示例1：

输入： 网格 = {{a,b,c},{d,r,f},{g,h,i}}, 字=“abc” 输出： {{0,0}} 解释： 从(0,0)我们可以在水平向右方向找到“abc”。

这是我使用dfs的代码，我不知道我的代码怎么不能通过。任何人都可以看一下吗？谢谢：）！

class Solution:
    def searchWord(self, grid, word):
        res = []
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if self.dfs(i, j, grid, word):
                    res.append([i, j])
                    
        return sorted(res) if res else []
            
            
      
    def dfs(self, row, col, grid, word):
        if not word:
            return True

        if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]) or grid[row][col] != word[0] :
            return False

        #backtracking
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

        grid[row][col] = '#'
        for dr, dc in directions:
            if self.dfs(row + dr, col + dc, grid, word[1:]):
                return True
        grid[row][col] = word[0]
        return False   

我的代码有错误或问题

Answer 1

您的解决方案的问题在于它允许“之字形”。

假设测试网格是：

a b a b
a b e b
e b e b

搜索词是“abb”。正确的解决方案应该返回 []，但您的解决方案将返回 [0,0] 和 [0,2]，使用以下路线：

[0,0]'a'->[0,1]'b'->[1,1]'b'
[0,2]'a'->[0,3]'b'->[1,3]'b'

我在这里更新了您的解决方案，进行了以下更改：

1. 为

   dfs

   添加了一个新参数，名为

   cur_direction

   ，默认为

   None

2. 当

   dfs

   进行递归调用时，当前方向会沿着
传递
3. 如果cur_direction不为null，那么我们不会遍历所有方向，我们只在当前方向继续搜索
4. 我删除了

   set grid[row][col] = '#'

   的代码，然后恢复了它，因为这个解决方案确保我们在跟踪单词时无法返回到之前的位置。

class Solution:
    def searchWord(self, grid, word):
        res = []
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if self.dfs(i, j, grid, word):
                    res.append([i, j])
                    
        return sorted(res) if res else []
            
      
    def dfs(self, row, col, grid, word, cur_direction=None):
        if not word:
            return True
        
        if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]) or grid[row][col] != word[0] :
            return False
        
        # If a direction was passed in, continue searching in that direction.
        if cur_direction:
            return self.dfs(row + cur_direction[0], col + cur_direction[1], grid, word[1:], cur_direction)
            
        #backtracking
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

        for dr, dc in directions:
            if self.dfs(row + dr, col + dc, grid, word[1:], (dr, dc)): # Pass along the direction
                return True
        grid[row][col] = word[0]
        return False   

我已经确认这通过了 GeeksForGeeks 上的所有 1120 个测试用例。