题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
解题思路:递归+回溯
首先遍历每一个board中的字符,如果该字符和word的第一个字符相等,就从这个位置进行匹配搜索,如果能够找到word,就返回true,board中可能存在多个字符合word中的第一个字符相等的情况,只要任一个位置能够匹配到,就直接返回true
因为同一个单元格内的字符不能重复使用,需要使用一个额外的数组标记那些单元格被访问过了
具体匹配搜索递归算法如下:
- 定义递归函数:process(char[][] board, String word, int x, int y, int index)
- 含义:从board[x][y]开始与word的第index个位置往后继续匹配,如果能够找到匹配的字符,返回true,否则返回false
- 递归终止的条件:
- 如果 board[x][y] != word.charAt(index):显然不匹配,返回false
- 否则,board当前位置的字符和word的第index个字符匹配,如果index==word.length()-1:已经全部匹配了,返回true
- 否则board[x][y]与 word.charAt(index)匹配,继续寻找board中下一个位置与word.charAt(index+1)匹配:
- 下一个位置有两个(边界情况,只能向两个方向走)或四个可选择的位置,依次遍历所有可能的位置,假设下一个位置为board[nextX][nextY]:
- 如果 flag[nextX][nextY]=false并且 board[nextX][nextY] == word.charAt(index+1):
- 令flag[nextX][nextY] = true
- result = process(board,word,nextX,nextY,index+1)
- 如果result=true,直接返回true
- 否则,说明从board[nextX][nextY]位置开始搜索没有匹配到,进行回溯,令flag[nextX][nextY] = flase
- 如果 flag[nextX][nextY]=false并且 board[nextX][nextY] == word.charAt(index+1):
- 所有位置都没有匹配,返回false
- 下一个位置有两个(边界情况,只能向两个方向走)或四个可选择的位置,依次遍历所有可能的位置,假设下一个位置为board[nextX][nextY]:
AC代码:
class Solution {
//标记哪些位置已经访问过
boolean[][] flag;
//四个方向
int[][] direct = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public boolean exist(char[][] board, String word) {
if (board.length*board[0].length<word.length()){
return false;
}
flag = new boolean[board.length][board[0].length];
for (int x = 0; x < board.length; x++) {
for (int y = 0; y < board[0].length; y++) {
if (board[x][y] == word.charAt(0)) {
flag[x][y] = true;
boolean result = process(board, word, x, y, 0);
if (result) {
return true;
}
flag[x][y] = false;
}
}
}
return false;
}
public boolean process(char[][] board, String word, int x, int y, int index) {
if (board[x][y]!=word.charAt(index)){
return false;
}else if (index==word.length()-1){
return true;
}
for (int i = 0; i < 4; i++) {
int nextX = x + direct[i][0];
int nextY = y + direct[i][1];
if (nextX >= 0 && nextX < board.length
&& nextY >= 0 && nextY < board[0].length
&& !flag[nextX][nextY]
&& board[nextX][nextY] == word.charAt(index + 1)) {
flag[nextX][nextY] = true;
boolean result = process(board, word, nextX, nextY, index + 1);
if (result) {
return true;
}
flag[nextX][nextY] = false;
}
}
return false;
}
}
文章来源地址https://www.toymoban.com/news/detail-641743.html
文章来源:https://www.toymoban.com/news/detail-641743.html
到了这里,关于79. 单词搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!