当前位置：首页 > news >正文

【LeetCode】剑指 Offer（6）

news 2025/9/4 13:09:32

写在前面：

题目：剑指 Offer 12. 矩阵中的路径 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

写在前面：

军训好累.......

题目：剑指 Offer 12. 矩阵中的路径 - 力扣（Leetcode）

题目的接口：

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {}
};

解题思路：

这道题不算很难，一眼看过去，

一下就能想到这就是用深度优先搜索（DFS），

说人话其实就是全部递归遍历一遍就行，

与所需字符串对应，符合要求就递归下去，不符合就返回。

只要注意一下细节上的问题就行。（注意走回头路这种情况）

具体思路：

1. 遍历整个矩阵

2. 通过递归判断矩阵中的每一个字符是否能够串成题目要求的字符串

3. 如果匹配成功返回true，如果匹配失败则返回false。

代码：

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {//矩阵的长和宽row = board.size(); col = board[0].size();//遍历整个矩阵for(int i = 0;i<row;i++){for(int j = 0;j<col;j++){//递归搜索是否存在与题目要求相同的字符串if(dfs(board, word, i, j, 0)){return true;}}}return false;}//可以建一个地方存放私有成员，方便我们访问
private://初始化int row, col;//递归函数的实现// k 是用来做为字符串word的下标的bool dfs(vector<vector<char>>& board, string word, int i, int j, int k){//如果出现越界或者匹配失败，返回falseif(i >= row || i < 0 || j >= col || j < 0 || board[i][j] != word[k]){return false;}//如果目标字符已经匹配完了，返回trueif(k == word.size() - 1){return true;}//细节：为了防止“走回头路”这种情况发生，改变位置原字符board[i][j] = '\0';//四个角度递归搜索，不符合条件返回false，符合的继续递归bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j - 1, k + 1);//搜素完后可以将原字符变回原样board[i][j] = word[k];//返回最后递归的结果return res;}
};