LeetCode 79.单词搜索(dfs+剪枝)
2021/10/11 23:46:27
本文主要是介绍LeetCode 79.单词搜索(dfs+剪枝),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述:来自LeetCode
思路:
看到这种搜索问题,很快就能想到dfs,以矩阵的每一个元素为起点和字符串的第一个元素为起点分别dfs,当我们遍历到字符串的最后一个字符也相等了,就说明word存在于网格中,故dfs要有一个参数m记录此时遍历的字符串的位置,将board和word也作为dfs函数参数,还有此刻遍历的矩阵的位置,我们用i,j来表示此时遍历到第i行第j列,题目里还有说同一个单元格的元素不能被重复用,故我们还要有一个标志单元格的元素是否被使用的标记数组。然后就可以开始dfs了,单元格的元素可以向四个方向搜索,只要有一个方向相等就可以。
dfs剪枝:
1.当m>=word.size()说明遍历字符串结束,return true;
2.当i,j表示的矩阵单元格的位置不合法时,return false;
3.当单元格内的元素和字符不相等时,return true;
class Solution { public: bool exist(vector<vector<char>>& board, string word) { bool st[10][10]; memset(st,false,sizeof(st)); for(int i=0;i<board.size();i++){ for(int j=0;j<board[0].size();j++){ bool is=dfs(board,word,i,j,0,st); if(is==true){ return true; } } } return false; } bool dfs(vector<vector<char>> &board,string &word,int i,int j,int m,bool st[10][10]){ if(m==word.length()) return true; if(i>board.size()-1||j>board[0].size()-1||i<0||j<0) return false; if(board[i][j]!=word[m]) return false; if(!st[i][j]){ st[i][j]=true; bool res= (dfs(board,word,i+1,j,m+1,st)||dfs(board,word,i-1,j,m+1,st)||dfs(board,word,i,j-1,m+1,st)||dfs(board,word,i,j+1,m+1,st)); st[i][j]=false; return res; } return false; } };
注意:dfs里面传值和传引用耗时是不一样的,传引用会比传值快很多
今日刷题任务完成~ 如有错误,欢迎指正~
这篇关于LeetCode 79.单词搜索(dfs+剪枝)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23增量更新怎么做?-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些?-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码?-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗?-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行?-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处?-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用?-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表?-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享