递归小小感想

发布时间:2023年12月20日

递归小小感想

今天刷一道深搜的题,对递归的一点感想,特此记录

[79. 单词搜索 - 力扣(LeetCode)](https://leetcode.cn/problems/word-search/description/)

image-20231220184920653

思路分析

这道题很明显是一个dfs问题,我们只需要从将每一个起点开始搜索直到单词结尾即可

  • 参数: (x,y) 指向矩阵的位置,u:指向当前应该匹配的单词位置
  • 我们只需要有一条路符合要求即可
  • 所以返回值为 boolean
class Solution {
    char[][] boa;
    char[] ch;
    int n,m;
    int[] dx={0,1,0,-1};
    int[] dy={1,0,-1,0};
    public boolean exist(char[][] board, String word) {
        boa=board;
        ch=word.toCharArray();
        n=board.length;
        m=board[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
              
                //问题一:为什么不是 return dfs(i,j,0) 
                
                //语句5
                if(dfs(i,j,0))return true;
            }
        }
        // dfs(0,0,0);
        return false;
        

    }
    boolean dfs(int x,int y,int u){
        if(ch[u]!=boa[x][y])return false;
        
         //语句4
        if(u==ch.length-1){
            return true; 
        }   
        char t=boa[x][y];
        boa[x][y]='*';
        for(int i=0;i<4;i++){
            int a=x+dx[i];
            int b=y+dy[i];
            if(a<0 || a>=n || b<0 ||b>=m || boa[a][b]=='*')continue;
            
            //2.为什么不是 dfs(i,j,u+1);
            
            if(dfs(a,b,u+1))return true;
            //dfs(a,u+1)为何出错???
        }
        //为什么要在这里恢复答案
        //当在当前位置(x,y)时,我们有可以向四个方向扩展,每个方向可以作为下一层的选择
        //所以,应该在四个方向遍历完之后恢复现场
        boa[x][y]=t;
        //3.
        return false;
    


    }
}

问题一

假设dfs算法是正确的

  • return dfs(i,j,0)

    如果这样写,只会返回以(0,0)为起点的搜索

  • if(dsf(i,j,0)) return true

    • 这样写,就只有当从 该点搜索到正确路径,返回true时才会结束遍历

    • 如果(0,0)开始搜索不符合条件就会开始下一个点搜索

    • 直至从(x,y)可以搜索到对应的路径,返回true结束该搜索

    • 如果所有点都作为起点不符合要求,就会执行最后的 return false;

问题二

  • dfs(i,j,u+1)

    • 这样的返回值与下一层搜索的返回值无关,最后只会返回 3. 处的 return false

    我们以图中示例举例,

    1. 假设我们搜索到 u=5,字母D,本层递归 返回 false
    2. 我们结束这层,返回倒数第二层,但是没有语句接受返回值,依旧会执行 3处的return false 而不会返回true
    3. 倒数第三层,。。。。同理,最后的结果就是 第一层的 3 处的 return false
  • if(dfs(i,j,u+1)) return ture;

    这样就是接受下一层的参数,只有当下一层返回false时就会结束该方法,

    我们同样以示例举例(假设n层)

    1. n: 执行语句4 返回true
    2. n-1 在没有执行到 3. 处语句时就会 执行if(dfs(i,j,u+1)) return ture;返回true 并结束本层,向上返回,直到第一层
    3. 1:依然执行 if语句,返回true
    4. 主方法中 执行 语句5 返回true

思考总结

  • 针对这种只要有一个满足即可的问题,我们只需要在搜索过程中寻找对应的正确答案并返回true
  • 如果所有方案搜索完毕,依旧没有true,说明没有符合要求的路径,返回false即可
文章来源:https://blog.csdn.net/weixin_45400340/article/details/135115987
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。