专栏首页Java小白成长之路剑指offer第10题:矩阵中的路径

剑指offer第10题:矩阵中的路径

矩阵中的路径

剑指Offer 12:矩阵中的路径【中等题】”

题目描述

方法:回溯

根据题目要求,需要我们从一个已知矩阵中找到一个可以挨个形成给定字符串的路径。如果有这条路径的话,我们需要返回true,如果没有的话,我们返回false,并且相同的字符不能重复使用。

从题目的解析上,我们可以很自然的联想到遍历整个矩阵,只是在遍历整个矩阵时,我们还需要保证每一次使用的元素不能重复,此时我们可以联想到回溯算法

首先我们需要建立一个访问矩阵vis,遍历整个矩阵,找到字符串的第一个字符,这个位置将会被我们用来作为开始的位置。然后以此处为中心,开始向四周进行扩展遍历,查看扩展中的路径,能否有一条到达字符串最后字符的路径,如果有的话,我们便找到了我们需要的这个字符串路径。对于每次我们遍历过的字符,需要将其位置设为true,表示当前位置已经被访问过了,然后再继续遍历下一个字符,向下递归。

使用回溯算法的时候,我们需要弄清楚一个问题,什么时候开始回溯?如果当前矩阵字符和字符串字符不匹配,那我们可以直接结束遍历,返回false即可;只有在当前字符匹配成功,但是后续的字符匹配不成功的时候,我们才需要把已经匹配的字符的vis进行回溯。

代码实现

	 private boolean[][] vis;//存放访问过的节点
    private int row ;
    private int col ;

    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || word == null) return false;
        row = board.length;
        col = board[0].length;
        vis = new boolean[row][col];
        for(int i = 0 ; i < row ; i ++){
            for(int j = 0 ; j < col ; j++){
                if(board[i][j] == word.charAt(0)){//寻找第一个符合的节点
                    boolean ans = help(board ,word , i , j , 0);
                    if(ans) return true;
                }
            }
        }
        return false;
    }
    private boolean help(char[][] board , String word , int x , int y , int index){
        if(index == word.length()) return true;//结束条件

        if(isOk(x,y) == false || board[x][y] != word.charAt(index)) return false;
        vis[x][y] = true;
        boolean ans =  help(board , word , x + 1 , y , index+1) ||
                        help(board , word , x - 1 , y , index+1) ||
                        help(board , word , x , y + 1 , index+1) ||
                        help(board , word , x , y - 1 , index+1);
        
        if(ans) return true;
        vis[x][y] = false; //回溯
        return false;
    }
    private boolean isOk(int x,int y){//用于判断当前位置是否是合法位置
        if(x < 0 || x >= row || y < 0 || y >= col) return false;
        if(vis[x][y]) return false;
        return true;
    }

【思考】

回溯算法在整个刷题系列里面出现的频次是非常高的。在我们后续刷题过程中,最主要的就是抓住两点,一个是回溯条件,还有一个就是结束条件,将这两个条件捋清楚之后,剩下的代码实现都是十分简洁的。

本文分享自微信公众号 - Java小白成长之路(Java_xiaobai),作者:鹏程万里

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer第11题:机器人运动范围

    此方法我们可以直接按照题目中的要求,将所有的方格全都访问一遍,由于所有的格子需要满足一个条件,连续性和单元格的坐标和小于n即可。

    鹏-程-万-里
  • 数学题:查找,快速幂,二进制,剪绳子

    各位小伙伴,又到周末啦~本周小白已经开始二刷《剑指offer》了,这次在LeetCode上面刷题,发现LeetCode上面的《剑指offer》和牛客上面的题目好...

    鹏-程-万-里
  • 回溯:系列经典题目

    对于回溯算法,一开始接触感觉还是挺难的,随着刷到的题目的数量增多,慢慢也可以总结出来相应的套路出来。大家一起来看看下面的伪代码

    鹏-程-万-里
  • Semaphore流量控制和源码分析

    原文链接:https://www.jhonrain.org/2019/09/18/高并发-高并发-Semaphore源码解析和使用场景/

    用户6391658
  • 【leetcode刷题】T159-爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    木又AI帮
  • C#版(击败96.64%的提交) - Leetcode 728. 自除数 - 题解

    Leetcode 728 - Self Dividing Numbers 在线提交: https://leetcode-cn.com/problems/se...

    Enjoy233
  • golang之递归

    超蛋lhy
  • c语言内嵌汇编代码之constraint modifier中 & 的作用

    在阅读本文之前,请先阅读gcc的相关文档,确保对如何在c中使用汇编语言有个基本的认识。

    wangyuntao
  • 如何比较?Comparable还是Comparator

    我家开了个小卖店,为了实现数字化管理,我准备写个后台程序来对所有货物进行管理。首先定义了这个实体类,这个类就是“货物”类,num指的是他的编号,s指他的名称或描...

    naget
  • 漫画:贼简单的题目,但百分之99%的人都不会

    为大家分享一道本应很简单的题目,但是却因增加了特殊条件,而大幅增加了难度。话不多说,直接看题。

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券