注意：如果用 Set 或者是 boolean[][]来标记字符位置是否已经访问过，需要额外的空间 O(m*n).
关键点分析
遍历二维数组的每一个点，找到起始点相同的字符，做 DFS
DFS 过程中，要记录已经访问过的节点，防止重复遍历，这里（Java Code 中）用 * 表示当前已经访问过，也可以用 Set 或者是 boolean[][]数组记录访问过的节点位置。
是否匹配当前单词中的字符，不符合回溯，这里记得把当前 * 重新设为当前字符。如果用 Set 或者是 boolean[][]数组，记得把当前位置重设为没有访问过。
代码 (Java/Javascript/Python3)
Java Code
public class LC79WordSearch {
public boolean exist(char[][] board, String word) {
if (board == null || word == null) return false;
if (word.length() == 0) return true;
if (board.length == 0) return false;
int rows = board.length;
int cols = board[0].length;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// scan board, start with word first character
if (board[r][c] == word.charAt(0)) {
if (helper(board, word, r, c, 0)) {
return true;
}
}
}
}
return false;
}
private boolean helper(char[][] board, String word, int r, int c, int start) {
// already match word all characters, return true
if (start == word.length()) return true;
if (!isValid(board, r, c) ||
board[r][c] != word.charAt(start)) return false;
// mark visited
board[r][c] = '*';
boolean res = helper(board, word, r - 1, c, start + 1) // 上
|| helper(board, word, r + 1, c, start + 1) // 下
|| helper(board, word, r, c - 1, start + 1) // 左
|| helper(board, word, r, c + 1, start + 1); // 右
// backtracking to start position
board[r][c] = word.charAt(start);
return res;
}
private boolean isValid(char[][] board, int r, int c) {
return r >= 0 && r < board.length && c >= 0 && c < board[0].length;
}
}
Python3 Code
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m = len(board)
n = len(board[0])
def dfs(board, r, c, word, index):
if index == len(word):
return True
if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[index]:
return False
board[r][c] = '*'
res = dfs(board, r - 1, c, word, index + 1) or dfs(board, r + 1, c, word, index + 1) or dfs(board, r, c - 1, word, index + 1) or dfs(board, r, c + 1, word, index + 1)
board[r][c] = word[index]
return res
for r in range(m):
for c in range(n):
if board[r][c] == word[0]:
if dfs(board, r, c, word, 0):
return True
return False
