给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的3×4的矩阵中包含单词"ABCCED"（单词中的字母已标出）。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
|
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
|
提示：
1 <= board.length <= 200 1 <= board[i].length <= 200 board和word仅由大小写英文字母组成
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
直接dfs即可。
class Solution {
public int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
public char[][] board = null;
public String word = null;
int m = 0, n = 0;
public boolean exist(char[][] board, String word) {
this.board = board;
this.word = word;
m = board.length;
n = board[0].length;
char start = word.charAt(0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == start && dfs(i, j, 0)) {
return true;
}
}
}
return false;
}
public boolean dfs(int x, int y, int index) {
if (index == word.length() - 1) return word.charAt(index) == board[x][y];
if (word.charAt(index) != board[x][y]) return false;
char record = board[x][y];
board[x][y] = '0';
for (int d = 0; d < 4; d++) {
int newX = x + directions[d][0];
int newY = y + directions[d][1];
if (0 <= newX && newX < m && 0 <= newY && newY < n && dfs(newX, newY, index + 1)) return true;
}
board[x][y] = record;
return false;
}
}
|
复杂度
略
