79. 单词搜索
题目描述
输入一个 m x n 的字符网格 board 和一个字符串 word。
从某个格子出发，每一步移到上下左右相邻的格子，依次经过的字母若恰好拼出 word，就说 word 在网格中。同一条路径里一个格子最多用一次。
能拼出时返回 true，否则返回 false。
示例 1
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] word = "ABCCED" 输出：true
解释：沿 A→B→C→C→E→D 走，可以拼出。
示例 2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] word = "SEE" 输出：true
解释：从第 1 行末尾的 S 出发，向下走到 E，再向左到 E。
示例 3
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] word = "ABCB" 输出：false
解释：拼到 ABC 之后要回到已用过的 B，不允许。
数据范围
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word只含大小写英文字母。
进阶：若网格更大，能否用剪枝加快搜索？
解题思路
DFS 匹配并临时标记格子。
为什么正确
当前路径内格子不可重复。
复杂度分析
时间 O(mn·3^L)，额外空间 O(L)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def exist(self,b,w):
m,n=len(b),len(b[0])
def f(r,c,k):
if k==len(w):return True
if not(0<=r<m and 0<=c<n) or b[r][c]!=w[k]:return False
z=b[r][c];b[r][c]='#';ok=any(f(r+dr,c+dc,k+1) for dr,dc in((1,0),(-1,0),(0,1),(0,-1)));b[r][c]=z;return ok
return any(f(r,c,0) for r in range(m) for c in range(n))class Solution {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private char[][] b;
private String w;
private int m, n;
public boolean exist(char[][] board, String word) {
b = board; w = word;
m = board.length; n = board[0].length;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (f(r, c, 0)) return true;
return false;
}
private boolean f(int r, int c, int k) {
if (k == w.length()) return true;
if (!(0 <= r && r < m && 0 <= c && c < n) || b[r][c] != w.charAt(k)) return false;
char z = b[r][c];
b[r][c] = '#';
boolean ok = false;
for (int[] d : DIRS)
if (f(r + d[0], c + d[1], k + 1)) { ok = true; break; }
b[r][c] = z;
return ok;
}
}class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
function<bool(int, int, int)> f = [&](int r, int c, int k) {
if (k == (int)word.size()) return true;
if (!(0 <= r && r < m && 0 <= c && c < n) || board[r][c] != word[k]) return false;
char z = board[r][c];
board[r][c] = '#';
bool ok = false;
for (auto& d : dirs)
if (f(r + d[0], c + d[1], k + 1)) { ok = true; break; }
board[r][c] = z;
return ok;
};
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (f(r, c, 0)) return true;
return false;
}
};func exist(board [][]byte, word string) bool {
m, n := len(board), len(board[0])
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var f func(r, c, k int) bool
f = func(r, c, k int) bool {
if k == len(word) {
return true
}
if !(0 <= r && r < m && 0 <= c && c < n) || board[r][c] != word[k] {
return false
}
z := board[r][c]
board[r][c] = '#'
ok := false
for _, d := range dirs {
if f(r+d[0], c+d[1], k+1) {
ok = true
break
}
}
board[r][c] = z
return ok
}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if f(r, c, 0) {
return true
}
}
}
return false
}var exist = function(board, word) {
const m = board.length, n = board[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const f = (r, c, k) => {
if (k === word.length) return true;
if (!(0 <= r && r < m && 0 <= c && c < n) || board[r][c] !== word[k]) return false;
const z = board[r][c];
board[r][c] = '#';
const ok = dirs.some(([dr, dc]) => f(r + dr, c + dc, k + 1));
board[r][c] = z;
return ok;
};
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (f(r, c, 0)) return true;
return false;
};function exist(board: string[][], word: string): boolean {
const m = board.length, n = board[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const f = (r: number, c: number, k: number): boolean => {
if (k === word.length) return true;
if (!(0 <= r && r < m && 0 <= c && c < n) || board[r][c] !== word[k]) return false;
const z = board[r][c];
board[r][c] = '#';
const ok = dirs.some(([dr, dc]) => f(r + dr, c + dc, k + 1));
board[r][c] = z;
return ok;
};
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (f(r, c, 0)) return true;
return false;
};