LeetCode-79. 单词搜索
2022/2/3 23:15:55
本文主要是介绍LeetCode-79. 单词搜索,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目来源
79. 单词搜索
题目详情
给定一个 m x n
二维字符网格 board
和一个字符串单词 word
。如果 word
存在于网格中,返回 true
;否则,返回 false
。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1:
输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出: true
示例 2:
输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出: true
示例 3:
输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出: false
提示:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board
和word
仅由大小写英文字母组成
进阶: 你可以使用搜索剪枝的技术来优化解决方案,使其在 board
更大的情况下可以更快解决问题?
题解分析
- 本题很明显是深搜加回溯的题型,可以说这是一道回溯的模板题。
- 这个题目虽然很简单,但是在编码时也会有一些细节问题,比如需要设置isTravel矩阵来标识一个坐标是否被遍历过。而且为了避免以后的轮次中重复赋初始值,需要在回溯时将isTravel重新设置为false。
- 考虑到符合条件的单词可以从任意一个单元开始出发组成,所以需要遍历所有的矩阵单元。
class Solution { int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; boolean flag = false; boolean[][] isTravel; int n, m; public boolean exist(char[][] board, String word) { n = board.length; m = board[0].length; isTravel = new boolean[n][m]; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ char ch = board[i][j]; if(ch == word.charAt(0)){ isTravel[i][j] = true; dfs(board, word, 0, i, j); isTravel[i][j] = false; if(flag){ return true; } } } } return false; } private void dfs(char[][] board, String word, int pos, int x, int y){ if(flag){ return; } if(pos == word.length() - 1){ flag = true; return; } for(int i=0; i<4; i++){ int dx = x + dir[i][0]; int dy = y + dir[i][1]; if(dx >=0 && dx < n && dy >=0 && dy < m && !isTravel[dx][dy] && word.charAt(pos + 1) == board[dx][dy]){ isTravel[dx][dy] = true; dfs(board, word, pos + 1, dx, dy); isTravel[dx][dy] = false; } } } }
结果展示
这篇关于LeetCode-79. 单词搜索的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享