【剑指Offer】矩阵中的路径
发布日期:2022-02-10 08:55:13
浏览次数:33
分类:技术文章
本文共 1418 字,大约阅读时间需要 4 分钟。
题目
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。
[["a","b","c","e"],
["s","f","c","s"], ["a","d","e","e"]]但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。
思路
DFS+剪枝
基本思路跟力扣大佬差不多,但一开始写的时候数组的横纵坐标还搞反了,这一块以后尤其需要注意。
代码
class Solution {public: bool dfs(vector>& board, string word,int i,int j,int k){ int height = board[0].size(); int width = board.size(); int len = word.size(); if(i < 0 || i == width || j < 0 || j == height || word[k] != board[i][j]) return false; if(k == len - 1) return true; char tmp = board[i][j]; board[i][j] = '0'; bool res = dfs(board,word,i,j+1,k+1) || dfs(board,word,i,j-1,k+1) || dfs(board,word,i+1,j,k+1) || dfs(board,word,i-1,j,k+1); board[i][j] = tmp; return res; } bool exist(vector >& board, string word) { std::ios::sync_with_stdio(false); if(board.size() == 0){ return false; } int height = board.size(); int width = board[0].size(); for(int i = 0; i < height; i++) { for(int j = 0; j < width; j++) { if(dfs(board, word, i, j, 0)) return true; } } return false; } };
转载地址:https://blog.csdn.net/hanmin822/article/details/105551284 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月08日 21时14分03秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
LeetCode题解(0974):和可被K整除的子数组(Python)
2019-04-26
LeetCode题解(0981):基于时间的键值存储(Python)
2019-04-26
LeetCode题解(0992):K个不同呢的子数组(Python)
2019-04-26
LeetCode题解(1001):网格照明(Python)
2019-04-26
LeetCode题解(1044):最长重复子串(Python)
2019-04-26
LeetCode题解(1048):最长字符串链(Python)
2019-04-26
LeetCode题解(1072):按列翻转得到最大值等行数(Python)
2019-04-26
LeetCode题解(1086):前五科的均分(Python)
2019-04-26
LeetCode题解(1364):顾客的可信联系人数量(SQL)
2019-04-26
LeetCode题解(1369):获取最近第二次的活动(SQL)
2019-04-26
LeetCode题解(1378):使用唯一标识码替换员工ID(SQL)
2019-04-26
LeetCode题解(1384):按年度列出销售总额(SQL)
2019-04-26
LeetCode题解(1393):股票的资本损益(SQL)
2019-04-26
LeetCode题解(1398):购买了产品A和产品B却没有购买产品C的顾客(SQL)
2019-04-26
LeetCode题解(1407):排名靠前的旅行者(SQL)
2019-04-26
LeetCode题解(1412):查找成绩处于中游的学生(SQL)
2019-04-26
LeetCode题解(1421):净现值查询(SQL)
2019-04-26
LeetCode题解(1435):制作会话柱状图(SQL)
2019-04-26
LeetCode题解(1440):计算布尔表达式的值(SQL)
2019-04-26
文件服务器实现基本条件!
2019-04-26