求解一个DFS题（谜之Bug）

题目:给一个grid（char[][]）和一个word（String），在grid中找的这个word，并返回word的每个letter在grid中的位置。
example:
input:
        char[][] grid = {
                {'c', 'r', 'c', 'a', 'r', 's'},
                {'a', 'b', 'i', 't', 'n', 'b'},
                {'t', 'f', 'n', 'n', 't', 'i'},
                {'x', 's', 'i', 'i', 'p', 't'}
        };

        String word = "catnip";

output:
[0, 2]
[0, 3]
[1, 3]
[2, 3]
[3, 3]
[3, 4]
我的解法如下：
为什么找到第一个p之后，不会回到i，而是继续从p开始找了？

1. public class CheatingWord {
   
2.     public static void main(String[] args) throws Exception {
   
3.         char[][] grid = {
   
4.                 {'c', 'r', 'c', 'a', 'r', 's'},
   
5.                 {'a', 'b', 'i', 't', 'n', 'b'},
   
6.                 {'t', 'f', 'n', 'n', 't', 'i'},
   
7.                 {'x', 's', 'i', 'i', 'p', 't'}
   
8.         };
   
9. 
   
10.         String word = "catnip";
    
11.         CheatingWord cw = new CheatingWord();
    
12.         cw.cheatingWord(word, grid);
    
13.     }
    
14. 
    
15.     public int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    
16. 
    
17.     public void cheatingWord(String word, char[][] grid) throws Exception {
    
18.         if (word == null || word.length() == 0) {
    
19.             throw new IllegalArgumentException("No word found!");
    
20.         }
    
21.         if (grid == null || grid.length == 0 || grid[0].length == 0) {
    
22.             throw new IllegalArgumentException("Invalid grid!");
    
23.         }
    
24. 
    
25.         List<List<int[]>> res = new ArrayList<>();
    
26.         List<int[]> list = new ArrayList<>();
    
27. 
    
28.         for (int i = 0; i < grid.length; i++) {
    
29.             for (int j = 0; j < grid[0].length; j++) {
    
30.                 dfs(word, grid, i, j, list, res, 0);
    
31.                 if (res.size() > 0) {
    
32.                     break;
    
33.                 }
    
34.             }
    
35.             if (res.size() > 0) {
    
36.                 break;
    
37.             }
    
38.         }
    
39.         System.out.println(1);
    
40.     }
    
41. 
    
42.     private void dfs(String word, char[][] grid, int i, int j, List<int[]> list, List<List<int[]>> res, int index) {
    
43.         if (index == word.length()) {
    
44.             res.add(new ArrayList<>(list));
    
45.             return;
    
46.         }
    
47. 
    
48.         if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
    
49.             return;
    
50.         }
    
51. 
    
52.         if (word.charAt(index) != grid[i][j]) {
    
53.             return;
    
54.         }
    
55. 
    
56.         char temp = grid[i][j];
    
57.         grid[i][j] = '#';
    
58. 
    
59.         for (int k = 0; k < dirs.length; k++) {
    
60.             list.add(new int[]{i, j});
    
61.             dfs(word, grid, i + dirs[k][0], j + dirs[k][1], list, res, index + 1);
    
62.             list.remove(list.size() - 1);
    
63.         }
    
64. 
    
65.         grid[i][j] = temp;
    
66.     }
    
67. }
    

复制代码

[/i][/i][/i][/i]

看不到全部的code，没明白楼主说的bug是什么，但有可能bug出在“list”这个variable上？每次进入dfs的时候，“list”应该是空的

miluChen 发表于 2020-9-5 22:09
看不到全部的code，没明白楼主说的bug是什么，但有可能bug出在“list”这个variable上？每次进入dfs的时候 ...

code的话，往下拉就能看到。
不好意思，我可能没讲清楚。
我重新讲一下：
这里dfs我是想把word在grid中的位置存到res中。按照example，我search到'p'的时候代表已经找到了个符合要求的list，我就放到res里面，然后return回递归的上一层。但是上一层不应该是'i'吗？我这里的bug是没有返回到递归的上一层，仍然留在'p'了。

miluChen 发表于 2020-9-5 22:09
看不到全部的code，没明白楼主说的bug是什么，但有可能bug出在“list”这个variable上？每次进入dfs的时候 ...

不知道我讲清楚了吗...
如果你方便的话，也可以加个w为x新语音聊一下，你可以把w为x新发我(七九四把四流二思琪),当交个题友啦哈哈。

当你search到p的时候 你的index 是5 你的word_length是6 并不满足line 43 的条件

所以当你在p时，你还会继续search 四个方向，并且你的res里会有4 个相同的结果。

1.         for (int k = 0; k < dirs.length; k++) {
   
2.             list.add(new int[]{i, j});
   
3.             dfs(word, grid, i + dirs[k][0], j + dirs[k][1], list, res, index + 1);
   
4.             list.remove(list.size() - 1);
   
5.         }

复制代码

dfs函数如果当前list是catni，到grid 有p这个字符的时候，每个方向都会push一次结果吧？

相当于

1.         for (int k = 0; k < dirs.length; k++) {
   
2.             list.add(new int[]{i, j});  // List is position for c, a, t, n, i. Trying to add position for p
   
3.             dfs(word, grid, i + dirs[k][0], j + dirs[k][1], list, res, index + 1); // dfs will return immediately while adding list to res
   
4.             list.remove(list.size() - 1); // Remove position for p, but loop will run 4 times (all directions)
   
5.         }

复制代码

像是leetcode #79 的翻版题， 可以参考leetcode的答案

提供一下我的解法，作为参考

1. class Solution:
   
2.     # @param board, a list of lists of 1 length string
   
3.     # @param word, a string
   
4.     # @return a boolean
   
5.     def exist(self, board, word):
   
6.         # edge case
   
7.         if not board:
   
8.             return False
   
9.         board = [list(x) for x in board]
   
10.         indexes = []
    
11.         for i in range(len(board)):
    
12.             for j in range(len(board[i])):
    
13. [/i]               if self._exist(board, i, j, word, 0, indexes):
    
14.                     print(indexes)
    
15.                     return True
    
16.         return False
    
17. 
    
18.     def _exist(self, board, i, j, word, k, indexes):
    
19.         '''Judge if word in (i, j) matches'''
    
20.         # out of bound
    
21. [i]        if i == len(board) or i == -1 or j == -1 or j == len(board):
    
22.             return False
    
23. 
    
24.         temp = board[j]
    
25.         
    
26.         if temp == '*': # already visited
    
27.             return False
    
28.         
    
29.         if not temp == word[k]:
    
30.             return False
    
31. 
    
32.         if k == len(word) -1 :
    
33.             return True
    
34. 
    
35.         board[j] = '*'
    
36.         indexes.append((i, j))
    
37.         if self._exist(board, i+1, j, word, k+1, indexes) or \
    
38.             self._exist(board, i-1, j, word, k+1, indexes) or \
    
39.             self._exist(board, i, j-1, word, k+1, indexes) or \
    
40.             self._exist(board, i, j+1, word, k+1, indexes):
    
41.             return True
    
42. 
    
43.         board[j] = temp
    
44.         indexes.pop()
    
45.         return False
    
46.         
    
47.         

复制代码

[/i]

landshark 发表于 2020-9-6 07:02
像是leetcode #79 的翻版题， 可以参考leetcode的答案

谢谢，这题我是有做过。我的解法也是一个思路，但是还是有点小问题。不过fixed了。