单词搜索
题目描述:给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例说明请见LeetCode官网。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-search/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一:回溯算法
首先,直接判断2种特殊场景:
- 如果要匹配的字符串为空,直接返回true;
- 如果board数组为空,直接返回false。
否则,先声明一个和board同样大小的boolean类型的数组,记录当前单元格是否已经走过,然后遍历board的每一个字符,对每一个字符和word第一个字符相等的时候,调用回溯方法进行判断以当前字符为起点是否能够匹配word字符串,如果能返回true,否则继续遍历下一个字符。最后,如果没有匹配成功,返回false。
public class LeetCode_079 {
public static boolean exist(char[][] board, String word) {
/**
* 如果要匹配的字符串为空,直接返回true
*/
if (word == null || word.length() == 0) {
return true;
}
/**
* 如果board数组为空,直接返回false
*/
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
/**
* 声明一个和board同样大小的boolean类型的数组,记录当前单元格是否已经走过
*/
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
/**
* 对每一个字符和word第一个字符相等的时候,调用方法进行判断
*/
if (board[i][j] == word.charAt(0) && exist(board, visited, word, i, j, 0)) {
return true;
}
}
}
return false;
}
/**
* 回溯算法
*
* @param board 原字符网格
* @param visited 和board大小相同的boolean类型的网格,标识当前字符是否走过
* @param word 要匹配的单词
* @param startX 当前单元格的x坐标
* @param startY 当前单元格的y坐标
* @param pos 当前已经匹配了几个字符
* @return
*/
private static boolean exist(char[][] board, boolean[][] visited, String word, int startX, int startY, int pos) {
if (board[startX][startY] != word.charAt(pos)) {
// 如果当前单元格和要匹配的字符不同,直接返回false
return false;
} else if (pos == word.length() - 1) {
// 如果已经匹配的字符数和word的长度相等,则说明已经匹配成功,返回true
return true;
}
visited[startX][startY] = true;
// 当前单元格可以往四个方向移动
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
boolean result = false;
for (int[] dir : directions) {
int nextStartX = startX + dir[0], nextStartY = startY + dir[1];
if (nextStartX >= 0 && nextStartX < board.length && nextStartY >= 0 && nextStartY < board[0].length) {
if (!visited[nextStartX][nextStartY]) {
boolean flag = exist(board, visited, word, nextStartX, nextStartY, pos + 1);
if (flag) {
result = true;
break;
}
}
}
}
visited[startX][startY] = false;
return result;
}
public static void main(String[] args) {
char[][] board = new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
// 测试用例,期望返回: true
System.out.println(exist(board, "ABCCED"));
}
}
【每日寄语】 逆境、是非来临,心中要持一“宽”字。