selected_coding_interview/docs/79. 单词搜索.md
本问题是典型的回溯问题，需要使用深度优先搜索（DFS）+ 剪枝解决。
{:width=500}
board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。k = len(word) - 1 ，即字符串 word 已全部匹配。board[i][j] 修改为 空字符 '' ，代表此元素已访问过，防止之后搜索时重复访问。或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。board[i][j] 元素还原至初始值，即 word[k] 。res ，代表是否搜索到目标字符串。使用空字符（Python:
'', Java/C++:'\0'）做标记是为了防止标记字符与矩阵原有字符重复。当存在重复时，此算法会将矩阵原有字符认作标记字符，从而出现错误。
<,,,,,,,,,,,,,,,,,>
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i, j, k):
if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
if k == len(word) - 1: return True
board[i][j] = ''
res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
board[i][j] = word[k]
return res
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i, j, 0): return True
return False
class Solution {
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if (dfs(board, words, i, j, 0)) return true;
}
}
return false;
}
boolean dfs(char[][] board, char[] word, int i, int j, int k) {
if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
if (k == word.length - 1) return true;
board[i][j] = '\0';
boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
board[i][j] = word[k];
return res;
}
}
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
rows = board.size();
cols = board[0].size();
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if (dfs(board, word, i, j, 0)) return true;
}
}
return false;
}
private:
int rows, cols;
bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;
if (k == word.size() - 1) return true;
board[i][j] = '\0';
bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
board[i][j] = word[k];
return res;
}
};
在代码中，$M, N$ 分别为矩阵行列大小， $K$ 为字符串 word 长度。