【重点】【回溯】【DFS】79.单词搜索
2023-12-19 05:27:34
题目
注意:此题跟岛屿的数量对比来看,增加了回溯的过程,岛屿题并无回溯。
法1:DFS
必须掌握方法!
class Solution {
public boolean exist(char[][] board, String word) {
char[] charArr = word.toCharArray();
int m = board.length, n = board[0].length;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int[][] used = new int[m][n];
if (dfs(board, charArr, used, i, j, 0)) {
return true;
}
}
}
return false;
}
public boolean dfs(char[][] board, char[] charArr, int[][] used, int i, int j, int curIndex) {
if (i < 0 || i >= board.length
|| j < 0 || j >= board[0].length
|| used[i][j] == 1
|| curIndex >= charArr.length
|| board[i][j] != charArr[curIndex]) {
return false;
}
if (curIndex == charArr.length - 1 && board[i][j] == charArr[curIndex]) {
return true;
}
used[i][j] = 1;
boolean res = dfs(board, charArr, used, i - 1, j, curIndex + 1)
|| dfs(board, charArr, used, i + 1, j, curIndex + 1)
|| dfs(board, charArr, used, i, j - 1, curIndex + 1)
|| dfs(board, charArr, used, i, j + 1, curIndex + 1);
if (res) {
return true;
} else {
used[i][j] = 0;
return false;
}
}
}
文章来源:https://blog.csdn.net/Allenlzcoder/article/details/135074727
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!