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
仅由大小写英文字母组成
二、回溯法
1、对board
数组进行循环查找,找到与word
首字母相同的元素[i,j]
2、以[i,j]
为根,开始对board
进行深度优先搜索,对[i-1,j]
、[i+1,j]
、[i,j-1]
、[i,j+1]
四个元素进行判断,是否已经被搜索过(需要维护一个二维数组visit
,用于记录board
中的元素是否被搜索过),是否等于word
中的第index
元素(index
根据搜索的次数不断增加),等于就继续递归,如果四个都不等于就返回false
。
3、不需要把所有可能搜索出来,只需要有一个满足条件的,就可以返回true
,停止搜索了。
public class Solution {
private static final int[][] DIRECTIONS = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
private int rows;
private int cols;
private int len;
private boolean[][] visited;
private char[] charArray;
private char[][] board;
public boolean exist(char[][] board, String word) {
rows = board.length;
if (rows == 0) {
return false;
}
cols = board[0].length;
visited = new boolean[rows][cols];
this.len = word.length();
this.charArray = word.toCharArray();
this.board = board;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (dfs(i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(int x, int y, int begin) {
if (begin == len - 1) {
return board[x][y] == charArray[begin];
}
if (board[x][y] == charArray[begin]) {
visited[x][y] = true;
for (int[] direction : DIRECTIONS) {
int newX = x + direction[0];
int newY = y + direction[1];
//判断该点是否越界或已遍历过
if (inArea(newX, newY) && !visited[newX][newY]) {
if (dfs(newX, newY, begin + 1)) {
return true;
}
}
}
visited[x][y] = false;
}
return false;
}
private boolean inArea(int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
}