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

一般的dfs（比如permutation，subsets）是以下的格式：

1. public void main(){
   
2.     dfs();
   
3. }
   
4. 
   
5. public void dfs(){
   
6.     for(){
   
7.        dfs();
   
8.    }
   
9. }

复制代码

但是那几道word search, word squares是以下形式：

1. public void main(){
   
2.     for(){
   
3.         for(){
   
4.             dfs();
   
5.         }
   
6.     }
   
7. }
   
8. 
   
9. public void dfs(){
   
10.     for(){
    
11.        dfs();
    
12.    }
    
13. }
    

复制代码

在主程序里面，对二维矩阵里面的每一个格子做dfs，是不是矩阵的dfs都需这么写？可以像permutation那样的格式写吗？permutation可以看成一维的，但是主程序里面没有for循环啊。有些费解。

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]开始去探索是否有满足的需求，所以需要下面两组循环。  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;
        }
    }
}

我的permutation是这么写的,在主程序里面没有for loop。不知道是不是可以把word search，word squares也写成这样。
[i][i][i]

1. 
   
2.     public List<List<Integer>> permute(int[] nums) {
   
3.         if(nums==null)
   
4.             return null;
   
5.         
   
6.         List<List<Integer>> res = new ArrayList<List<Integer>>();
   
7.         List<Integer> temp = new ArrayList<Integer>();
   
8.         HashSet<Integer> set = new HashSet<Integer>();
   
9.         helper(nums,set,temp,res);
   
10.         return res;
    
11.     }
    
12.    
    
13.     private void helper(int[] nums, HashSet<Integer> set, List<Integer> temp, List<List<Integer>> res){
    
14.             if(temp.size()==nums.length){
    
15.             res.add(new ArrayList<Integer>(temp));
    
16.             return;
    
17.             }
    
18.         
    
19.         for(int i=0;i<nums.length;i++){
    
20.             if(set.contains(nums))
    
21.                 continue;
    
22.             temp.add(nums);
    
23.             set.add(nums);
    
24.             helper(nums,set,temp,res);
    
25.             set.remove(nums);
    
26.             temp.remove(temp.size()-1);
    
27.         }
    
28.     }

复制代码

补充内容 (2018-5-20 11:46):
@肥宅快乐水,你上面那个code有没有非bit的写法？[/i][/i][/i]

收到你的消息 我晚点看看你的这个问题回复在这里 - 一条消息系统要扣三分哟

一回事，dfs就是走图的每一个节点。

先回答你第二个问题好了，每一个[i][j] 相当于图中每一个节点，不过在这个题中没有别的方法走到这个[i][j]节点上。

对于permutation, 或者 subset ，是一样的。只不过你的起始点是可以走到每一个节点上的。

就以permutation为例好了，你当然也完全可以先选一个起始点， 然后再做perm。

1. class Solution {
   
2.     public List<List<Integer>> permute(int[] nums) {
   
3.         int n = nums.length;
   
4.         for(int i = 0; i < n; i++)
   
5.         {
   
6.             List<Integer> list = new ArrayList<>();
   
7.             list.add(nums[i]);
   
8.             dfs(nums, 1 << i, list);
   
9.         }
   
10.         return re;
    
11.     }
    
12. 
    
13. 
    
14.     List<List<Integer>> re = new ArrayList<>();
    
15. 
    
16.     void dfs(int[] n, int k, List<Integer> list)
    
17.     {
    
18.         if((1 << n.length) - 1 == k)
    
19.         {
    
20.             re.add(new ArrayList<>(list));
    
21.             return;
    
22.         }
    
23.         for(int i = 0; i < n.length; i++)
    
24.         {
    
25.             if(((1 << i) & k) != 0) continue;
    
26.             k |= 1 << i;
    
27.             list.add(n[i]);
    
28.             dfs(n, k, list);
    
29.             list.remove(list.size() - 1);
    
30.             k &= ~(1 << i);
    
31.         }
    
32.     }
    
33. }

复制代码

shuatizhe 发表于 2018-5-20 08:06
我的permutation是这么写的,在主程序里面没有for loop。不知道是不是可以把word search，word squares也写 ...

不该装b的，我错了。
你的perm写的完全没有问题，我也会这么写。

这样说吧， word search一样可以这么写， 只不过这样就不符合题意了，需要满足上下左右走的这四个方向。

如果perm这个题加一个条件， 比如给出【5,6,7】开头的所有perm，一共有【0-9】的数字。那么你的perm就不会这么写了。一定是进dfs之前有一个for loop的。

pxu 发表于 2018-5-20 00:53
收到你的消息 我晚点看看你的这个问题回复在这里 - 一条消息系统要扣三分哟

谢谢了啊：）如果不忙的话，期待看到你的答案

shuatizhe 发表于 2018-5-25 23:14
谢谢了啊：）如果不忙的话，期待看到你的答案

My computer was broken and I have to fix it early nex week and look at this topic afterwards. Sorry for that.

谢谢，没关系的，fix computer重要 ：）

关于Subsets, Permutations, Combination Sum, Palindrome Partioning， 有人整理出通用的模板。
https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)

我没做过word search, word squares，这部分等我做完再恢复。不好意思

专门做了你问的这几个题目，我觉得应该按照给的数组类型（一维数组还是二维）去分析，
比如Permuation, 比如给的是一维数组[1,2,3]. 第一次循环，从item 0 开始到最后一个元素，依次加入后面的元素。通过if(tempList.contains(nums[i])) continue; 来跳过重复的。得出[1,2,3]
backtack后，从最后一个元素3被pop out,因为元素3就是最后一个元素，所有这个循环结束；
再次backtack, 把2 Pop out, 把3加进去 变成 [1,3],然后进入下一个backtrack 把2 加进来，得出 [1,3,2]。
解释起来比较费劲， 不好意思。@shuatizhe
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
         List<List<Integer>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), nums);
        return list;
    }


private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
    if( tempList.size()== nums.length){
        list.add(new ArrayList<>(tempList));
    }
    else{
        for(int i = 0; i < nums.length; i++){
            if(tempList.contains(nums[i])) continue;
            tempList.add(nums[i]);
            backtrack(list, tempList, nums);
            tempList.remove(tempList.size() - 1);
        }
    }
}
}