剑指Offer：矩阵中的路径

电玩女神 2022-11-12 04:29 150阅读 0赞

![转自leetcode剑指Offer][leetcode_Offer]矩阵搜索题目，按照题解说的，可用DFS（深度优先搜索）和剪枝解决，首先在矩阵中找到和路径开头字符一样的位置i，j，之后递归，看上下左右深度搜索是否能找到满足的路径，具体代码如下：

class Solution { 
        String words;
        public boolean exist(char[][] board, String word) { 
            words=word;
            for(int i=0;i<board.length;i++){ 
                for(int j=0;j<board[0].length;j++){ 
                	//遍历矩阵，看以board[i][j]开头的元素是否满足
                    if(traverseBack(i,j,0,board)) return true;
                }
            }
            return false;
        }
        public boolean traverseBack(int i,int j,int k,char[][] board){ 
        	//超出边界或路径重复或路径不相等都返回false
            if(i<0||j<0||i>board.length-1||j>board[0].length-1||words.charAt(k)!=board[i][j])
            return false;
            //长度相等了则说明一路都是满足的，即有满足条件的路径，返回true
            if(k==words.length()-1) return true;
            //记录走过的路径
            board[i][j]='\0';
            //下上右左搜索符合条件的路径
            boolean res=traverseBack(i+1,j,k+1,board)||traverseBack(i-1,j,k+1,board)||
            traverseBack(i,j+1,k+1,board)||traverseBack(i,j-1,k+1,board);
            //回溯，为了不影响之后的搜索
            board[i][j]=words.charAt(k);
            return res;
        }
    }

[leetcode_Offer]: /images/20221022/4f34139081294a3d9815f55e6422c11a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，150人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指Offer】12. 矩阵中的路径

题目描述判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向上下左右移动一个格子。如果一条路径经过了矩阵中的

àì夳堔傛蜴生んèń/ 2022年11月24日 16:21/ 0 赞/ 160 阅读

相关剑指Offer：矩阵中的路径

![转自leetcode剑指Offer][leetcode_Offer]矩阵搜索题目，按照题解说的，可用DFS（深度优先搜索）和剪枝解决，首先在矩阵中找到和路径开头字符一样的位

电玩女神/ 2022年11月12日 04:29/ 0 赞/ 151 阅读

相关剑指offer_矩阵中的路径

/ 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上

小灰灰/ 2022年06月08日 22:48/ 0 赞/ 165 阅读

相关《剑指offer》--012--矩阵中的路径

[《剑指offer》–目录索引][offer] 题目： > 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有 > 字符的路径。路径可以从矩阵中任意一格开

r囧r小猫/ 2022年06月01日 08:45/ 0 赞/ 161 阅读

相关剑指Offer-矩阵中的路径

题目描述请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个

太过爱你忘了你带给我的痛/ 2022年05月22日 03:10/ 0 赞/ 176 阅读

相关剑指offer 矩阵中的路径回溯

coding:utf-8 !/usr/bin/env python Time: 2018/6/11 9:09

我不是女神ヾ/ 2022年05月21日 23:40/ 0 赞/ 165 阅读

相关剑指Offer-矩阵中的路径

题目描述请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个

青旅半醒/ 2022年04月25日 05:58/ 0 赞/ 141 阅读

相关【剑指Offer】矩阵中的路径（回溯）

题目链接：[https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc?tpId=13&tqId=11

本是古典何须时尚/ 2022年03月12日 19:47/ 0 赞/ 171 阅读

相关剑指Offer12:矩阵中的路径

请设计一个函数，用来判断矩阵中是否存在包含某一条字符串的所有路径，路径可以从任意一格开始，上下左右，一条路径经过矩阵某一格，不可以再次进入。在 char[][] nu

缺乏、安全感/ 2022年02月18日 16:55/ 0 赞/ 212 阅读

相关剑指offer：矩阵中的路径

试题：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子

约定不等于承诺〃/ 2021年06月24日 16:10/ 0 赞/ 371 阅读