给定一个 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
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
boolean[][] book = new boolean[m][n]; // 默认值为false
// for (int i = 0; i < m; i++) {
// Arrays.fill(book[i], false);
// }
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
boolean flag = dfs(board, word, i, j, 0, book);
if (flag) {
return true;
}
}
}
return false;
}
boolean dfs(char[][] board, String word, int i, int j, int cur, boolean[][] book) {
if (board[i][j] != word.charAt(cur)) { // 不匹配，直接返回
return false;
} else if (cur == word.length()-1) {
return true;
}
book[i][j] = true;
boolean res = false;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上 下 左 右
for (int[] dir : directions) {
int new_i = i+dir[0];
int new_j = j+dir[1];
if (new_i>=0 && new_i=0 && new_j
- book[m][n] 用来记录当前状态已匹配的字符序列，已匹配的字符置为 true，并在回溯时恢复为 false；在匹配下个字符时，不搜索 book[i][j] == true 位置的元素，避免字母的重复使用。
- 搜索起点在主函数中编写（两层 for 循环；每个结点均可作为起点）。
- “上下左右” 递归写法：dir = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };（代码 27-31 行）。
一道回溯法的中等题，比较容易超时。
Original: https://www.cnblogs.com/higuai/p/16434441.html
Author: 小小小海怪
Title: Leedcode 79. 单词搜索
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/588325/
转载文章受原作者版权保护。转载请注明原作者出处！