京公网安备11010502063487号给定一个字母网格和一个单词，判断单词能否由网格中相邻（上下左右）的格子依次连成，同一个格子在一条路径里不能重复使用。做法是回溯（深度优先搜索）：对每个格子作为起点，尝试匹配单词的第一个字符，然后向四个方向继续匹配下一个字符，走过的格子标记为已使用，一条路走不通就撤销标记退回来。本文用真实数据展示两个常见的错误（不撤销标记、完全不标记）各自会错多少，展示最坏情形下的搜索规模，给出五种语言的实现，并把搜索过程做成分步演示。
完整题目见官方页面（链接在文末）。基准解是用显式栈的深度优先搜索，每个栈状态自己带着"已经使用的格子"集合，不修改网格，与原地标记再撤销的递归是两种不同的写法。一共 15 组用例，覆盖：官方三个示例、单个格子、单词比网格长、要求重复使用同一个格子的情形（AA 里找 AAA 应该失败）、需要转弯的路径：
输入 [["ABCE","SFCS","ADEE"],"ABCCED"] 输出 true 输入 [["ABCE","SFCS","ADEE"],"SEE"] 输出 true 输入 [["ABCE","SFCS","ADEE"],"ABCB"] 输出 false 输入 [["A"],"A"] 输出 true 输入 [["A"],"B"] 输出 false 输入 [["AB"],"BA"] 输出 true
标记已使用的格子有两个环节都容易出错：第一，一条路径走不通、退回来时，必须把标记撤销，否则别的路径就用不了这个格子；第二，如果压根不标记，同一个格子就会在一条路径里被重复使用。下面是两种错误写法与 solve 的真实结果，最后一行是在 20000 组随机数据上统计的错误比例：
# 两种错误写法：标记后不撤销 / 完全不标记 ['ABCE', 'SFCS', 'ADEE'], 'ABCCED': 不撤销 -> True；不标记 -> True；solve -> True ['ABCE', 'SFCS', 'ADEE'], 'SEE': 不撤销 -> True；不标记 -> True；solve -> True ['ABCE', 'SFCS', 'ADEE'], 'ABCB': 不撤销 -> False；不标记 -> True；solve -> False ['AA'], 'AAA': 不撤销 -> False；不标记 -> True；solve -> False ['AB', 'CD'], 'ABDC': 不撤销 -> True；不标记 -> True；solve -> True 随机 20000 组：不撤销的写法出错 786 组（3.9%），不标记的写法出错 2697 组（13.5%）
官方示例里不撤销的写法在 ABCCED 和 SEE 上碰巧是对的，ABCB 也对（答案是 False）；不标记的写法则在 ABCB（B 需要重复使用）上错误地返回了 True，AA 里找 AAA 也错误地返回 True。随机数据里（网格和单词的字母都只有 a、b，重复使用同一格的机会很多），不撤销的写法错了 3.9%，不标记的写法错了 13.5%。所以官方示例通过并不代表这两个环节都是对的。
dfs(i, j, k) 表示从格子 (i, j) 出发，匹配单词从第 k 个字符起的后缀：k 等于单词长度说明全部匹配，返回真；越界或者格子字符与 word[k] 不符，返回假；否则把这个格子临时改成 #（不会出现在单词里，等价于"已使用"），依次向下、上、右、左递归，得到结果后把格子改回原来的字符，再返回。最外层对每个格子作为起点尝试一遍。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；Java、Go、C++ 直接在传入的网格上修改（并恢复），Python 和 JavaScript 先复制成字符二维数组。
Python · 解法代码def solve(board, word): g = [list(r) for r in board] m, n = len(g), len(g[0]) def dfs(i, j, k): # 从 (i, j) 出发，匹配 word[k:] if k == len(word): return True if i < 0 or j < 0 or i >= m or j >= n or g[i][j] != word[k]: return False ch = g[i][j] g[i][j] = "#" # 标记为已使用：同一个格子不能重复用 found = 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) g[i][j] = ch # 回溯：撤销标记，让别的路径还能用这个格子 return found return any(dfs(i, j, 0) for i in range(m) for j in range(n))
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [["ABCE","SFCS","ADEE"],"ABCCED"] → true [["ABCE","SFCS","ADEE"],"SEE"] → true [["ABCE","SFCS","ADEE"],"ABCB"] → false [["A"],"A"] → true [["A"],"B"] → false [["AB"],"BA"] → true
Java · 解法代码class Solution { private char[][] g; private String word; private int m, n; public boolean exist(char[][] board, String word) { this.g = board; this.word = word; m = board.length; n = board[0].length; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (dfs(i, j, 0)) return true; return false; } private boolean dfs(int i, int j, int k) { // 从 (i, j) 出发，匹配 word[k..] if (k == word.length()) return true; if (i < 0 || j < 0 || i >= m || j >= n || g[i][j] != word.charAt(k)) return false; char ch = g[i][j]; g[i][j] = '#'; // 标记为已使用：同一个格子不能重复用 boolean found = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) || dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1); g[i][j] = ch; // 回溯：撤销标记，让别的路径还能用这个格子 return found; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [["ABCE","SFCS","ADEE"],"ABCCED"] → true [["ABCE","SFCS","ADEE"],"SEE"] → true [["ABCE","SFCS","ADEE"],"ABCB"] → false [["A"],"A"] → true [["A"],"B"] → false [["AB"],"BA"] → true
Go · 解法代码func exist(board [][]byte, word string) bool { m, n := len(board), len(board[0]) var dfs func(i, j, k int) bool // 从 (i, j) 出发，匹配 word[k:] dfs = func(i, j, k int) bool { if k == len(word) { return true } if i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word[k] { return false } ch := board[i][j] board[i][j] = '#' // 标记为已使用：同一个格子不能重复用 found := dfs(i+1, j, k+1) || dfs(i-1, j, k+1) || dfs(i, j+1, k+1) || dfs(i, j-1, k+1) board[i][j] = ch // 回溯：撤销标记，让别的路径还能用这个格子 return found } for i := 0; i < m; i++ { for j := 0; j < n; j++ { if dfs(i, j, 0) { return true } } } return false }
$ go build -o bin . && ./bin < cases.jsonl [["ABCE","SFCS","ADEE"],"ABCCED"] → true [["ABCE","SFCS","ADEE"],"SEE"] → true [["ABCE","SFCS","ADEE"],"ABCB"] → false [["A"],"A"] → true [["A"],"B"] → false [["AB"],"BA"] → true
JavaScript · 解法代码function exist(board, word) { // board 是字符串数组；内部转成字符二维数组以便标记 const g = board.map((r) => r.split("")); const m = g.length, n = g[0].length; const dfs = (i, j, k) => { // 从 (i, j) 出发，匹配 word[k..] if (k === word.length) return true; if (i < 0 || j < 0 || i >= m || j >= n || g[i][j] !== word[k]) return false; const ch = g[i][j]; g[i][j] = "#"; // 标记为已使用：同一个格子不能重复用 const found = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) || dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1); g[i][j] = ch; // 回溯：撤销标记，让别的路径还能用这个格子 return found; }; for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) if (dfs(i, j, 0)) return true; return false; }
$ node run.js < cases.jsonl [["ABCE","SFCS","ADEE"],"ABCCED"] → true [["ABCE","SFCS","ADEE"],"SEE"] → true [["ABCE","SFCS","ADEE"],"ABCB"] → false [["A"],"A"] → true [["A"],"B"] → false [["AB"],"BA"] → true
C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { vector<vector<char>>* g; const string* word; int m, n; bool dfs(int i, int j, int k) { // 从 (i, j) 出发，匹配 word[k..] if (k == (int)word->size()) return true; if (i < 0 || j < 0 || i >= m || j >= n || (*g)[i][j] != (*word)[k]) return false; char ch = (*g)[i][j]; (*g)[i][j] = '#'; // 标记为已使用：同一个格子不能重复用 bool found = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) || dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1); (*g)[i][j] = ch; // 回溯：撤销标记，让别的路径还能用这个格子 return found; } public: bool exist(vector<vector<char>>& board, string w) { g = &board; word = &w; m = board.size(); n = board[0].size(); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (dfs(i, j, 0)) return true; return false; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [["ABCE","SFCS","ADEE"],"ABCCED"] → true [["ABCE","SFCS","ADEE"],"SEE"] → true [["ABCE","SFCS","ADEE"],"ABCB"] → false [["A"],"A"] → true [["A"],"B"] → false [["AB"],"BA"] → true
共 15 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 15/15 Java 通过 15/15 Go 通过 15/15 JavaScript 通过 15/15 C++ 通过 15/15
单词搜索的复杂度大致是 O(网格格子数 × 3^L)，L 是单词长度（每一步最多向 3 个新方向走）。最坏的情形是网格里全是同一个字母，单词是很多个这个字母再加上一个网格里没有的字母，这时每条路径都要走到底才发现最后一个字母对不上。我用 5×5 全是 a 的网格，统计单词是 L 个 a 加一个 b 时 dfs 的真实调用次数：
最坏情形：5×5 的网格全是 a，单词是 L 个 a 再加一个 b（永远找不到），dfs 的调用次数： L= 4: dfs 调用 3021 次，结果 False L= 8: dfs 调用 64605 次，结果 False L=12: dfs 调用 682301 次，结果 False L=16: dfs 调用 3873021 次，结果 False
L 每增加 4，调用次数依次增加 21.4 倍、10.6 倍、5.7 倍（3021、64605、682301、3873021）；增长比 3^4 = 81 倍慢，并且越来越慢，因为网格只有 25 个格子，路径不能重复使用格子，能走的方向数越到后面越少。L = 16 时就已经有近 400 万次调用。这也是为什么这道题的单词长度被限制在 15 以内。
Python 版本另外和显式栈的基准做了随机对拍，网格 1 到 3 行、1 到 4 列，网格和单词的字母都取自 a、b：
随机对拍 30000 组（1 到 3 行、1 到 4 列、字母取自 a、b 的网格，单词长 1 到 6（字母也取自 a、b，所以重复使用同一格的错误最容易暴露）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 15 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方的第一个示例，找 ABCCED。从 (0, 0) 的 A 出发，向下试 (1, 0) 的 S 不匹配，向上越界（没有记录），向右 (0, 1) 的 B 匹配……依次匹配 B、C，然后 C（(1, 2)），E（(2, 2)），D（(2, 1)），共 6 个字符。琥珀色是当前路径上的格子，蓝色是正在尝试的格子。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。