剑指Offer：矩阵中的路径

电玩女神 2022-11-12 04:29 145阅读 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 条评论，145人围观）

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

相关阅读

相关剑指offer 矩阵中的路径

[剑指offer题型分类及各题的解题思路与代码（<---点我跳转 ^ - ^）][offer_---_ _ -] 1、题目描述请设计一个函数，用来判断...

小鱼儿/ 2024年04月17日 15:48/ 0 赞/ 53 阅读

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

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

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

相关剑指offer_矩阵中的路径

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

た入场券/ 2022年04月11日 11:56/ 0 赞/ 124 阅读

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

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

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

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

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

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