请问dfs的一个题型写法问题

对于 79. Word Search，给出的是二维数组，需要对每个board[row][col]开始去探索是否有满足的需求，所以需要下面两组循环。  for(row=0;..){
        for(col=0;...){
            dfs();
        }
    }

在dfs里面，因为要上下左右的去探索，所以也会有一个4个方向的循－具体见我下面代码。感觉不能光去背模板，要具体情况，具体分析。 呵呵，解释起来太费劲，希望对你的理解有帮组。
class Solution {
    int dirs[][] = {{0, -1},{-1,0},{0, 1},{1, 0}};
   
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || word == null || word.length() == 0){
            return false;
        }
        int rows = board.length;
        int cols = board[0].length;
        int status[][] = new int[rows][cols];
        
        for(int row = 0; row < rows; row++){
            for(int col = 0; col < cols; col++){


                if(dfs(row, col, rows,cols,board, word,0, status) == true){
                   return true;
               }
               
            }
        }
        
        return false;
    }
   
    private boolean dfs(int row, int col, int rows, int cols, char[][] board, String word, int curr, int status[][]){
        if(curr == word.length()){
            return true;
        }else{
             if(row < 0 || row >= rows || col < 0 || col >= cols){
                return false;
             }
            
             if(status[row][col] == 0 && board[row][col] == word.charAt(curr)){   
                 status[row][col] = 1;
                 for(int dir[]: dirs){
                     int newRow = row + dir[0];
                     int newCol = col + dir[1];
                    
                    if(dfs(newRow, newCol,rows, cols, board, word, curr+1, status)){
                        return true;
                    }
            
                 }
                 status[row][col] = 0;
            }
         
            return false;
        }
    }
}

208.Implement Trie (Prefix Tree)也差不多。供你参考吧。

1. class Solution {
   
2.     int dirs[][] = {{0,-1},{-1,0},{0,1},{1,0}};
   
3.     int longestLen = 0;
   
4.     public List<String> findWords(char[][] board, String[] words) {
   
5.         Set<String> res = new HashSet<>();
   
6.         if(board == null || board.length == 0){
   
7.             return new ArrayList<String>(res);
   
8.         }
   
9.         
   
10.         TrieNode root = new TrieNode();
    
11.         for(String word: words){
    
12.             addWordToTrieNode(root, word);
    
13.         }
    
14.         
    
15.         int rows = board.length;
    
16.         int cols = board[0].length;
    
17.         boolean status[][] = new boolean[rows][cols];
    
18.         
    
19.         for(int row = 0; row < rows; row++){
    
20.             for(int col = 0; col < cols; col++){
    
21.                 dfs(row, col,rows,cols,board, root, res, status);
    
22.             }
    
23.         }
    
24.         
    
25.         return new ArrayList<String>(res);
    
26.     }
    
27.    
    
28.     private void dfs(int row, int col, int rows, int cols, char[][] board, TrieNode node, Set<String> res, boolean status[][]){
    
29.                
    
30.         if(row < 0 || row >= rows || col <0 || col >= cols || status[row][col]){
    
31.             return;
    
32.         }
    
33.         
    
34.         int k = board[row][col] - 'a';
    
35.         if(node.children[k] == null){
    
36.             return;
    
37.         }  
    
38.         
    
39.         if(node.children[k].word != null){
    
40.             res.add(node.children[k].word);
    
41.             node.children[k].word = null;
    
42.         }
    
43.         
    
44.         status[row][col] = true;   
    
45.         for(int dir[]: dirs){
    
46.             int newRow = row + dir[0];
    
47.             int newCol = col + dir[1];
    
48.             
    
49.             dfs(newRow, newCol, rows, cols, board, node.children[k], res, status);
    
50.         }
    
51. 
    
52.         status[row][col] = false;   
    
53.     }
    
54.    
    
55.     private void addWordToTrieNode(TrieNode root, String word){
    
56.         TrieNode p = root;
    
57.         for(char c: word.toCharArray()){
    
58.             if(p.children[c-'a'] == null){
    
59.                 p.children[c-'a'] = new TrieNode();
    
60.             }
    
61.             p = p.children[c-'a'];
    
62.         }
    
63.         p.word = word;
    
64.         
    
65.     }
    
66.    
    
67.     private class TrieNode{
    
68.         TrieNode children[] = new TrieNode[26];
    
69.         String word;
    
70.     }
    
71. }

复制代码

谢谢回复啊:)  你说的：”对于 79. Word Search，给出的是二维数组，需要对每个board[row][col]开始去探索是否有满足的需求，所以需要下面两组循环“。这个我知道，我的意思是permutation那道题也可以理解为一维数组，对每个元素开始搜索，所以需要一个一组循环，就像前面板凳那一层的大侠写的的那样：
for (int i = 0; i<nums.length; i++){
     dfs();
}
但是其实一般的permutation都不这么写，把从每个元素开始这一要求放到dfs里面去做。那同样，word search也可以在前面不用二重循环，而是直接把从每个board[row][col]开始去探索这一要求放到dfs里面去做。应该有这样的实现方式，但是写起来会很复杂，需要很多判断和剪枝。

不知道我说的对不对？

Permutation 那个可能也可以的，或者你自己试试，或者2哦有时间试试告诉你结果。

想了一下，也看了好几到题目的解法，觉得你的总结还是很到位的。对于一维数组的，好像多数可以用：具体的题目，比如permutation，combination, 还有phone number to letter(public void main(){
    dfs();
}

public void dfs(){
    for(){
       dfs();
   }
}

对于二维数组的，比如Word Search，你的归纳也很好的。我觉得没什么需要再做的了。你觉得呢？

对于这些题目的写法我倒是知道，问问题的初衷是想理清一些还不太清楚的概念已经验证一下不同的写法，不过现在看起来差不多了，谢谢回复：）