题目描述
思路解析动画文字版
记住两条主线：棋盘的 DFS 和字典树的指针「绑在一起同步走」；字典树没分支就剪枝、有结束标记就收词。下面每一帧都在套这套规则。
先把要找的三个单词 oat、pea、tea 压成一棵字典树（共享公共前缀），再让搜索从棋盘每个格子出发。下面演示几个有代表性的起点。
格子的字母 o 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "o"，沿着它接着往四周找下一个字母。
格子的字母 a 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "oa"，沿着它接着往四周找下一个字母。
格子的字母 t 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "oat"，沿着它接着往四周找下一个字母。
走到这里，字典树的这个节点挂着结束标记，意味着路径上的字母刚好拼成了目标单词 "oat"！把它收进答案。为了不重复收录，把这个单词从字典树上摘掉。
从这里往这个方向探一步，字母是 e。字典树里当前节点没有 e 这条分支，说明 "oate" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
从这里往这个方向探一步，字母是 p。字典树里当前节点没有 p 这条分支，说明 "oap" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
格子的字母 a 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "oa"，沿着它接着往四周找下一个字母。
从这里往这个方向探一步，字母是 p。字典树里当前节点没有 p 这条分支，说明 "oap" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
格子的字母 t 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "oat"，沿着它接着往四周找下一个字母。
从这里往这个方向探一步，字母是 e。字典树里当前节点没有 e 这条分支，说明 "oate" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
格子的字母 p 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "p"，沿着它接着往四周找下一个字母。
格子的字母 e 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "pe"，沿着它接着往四周找下一个字母。
格子的字母 a 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "pea"，沿着它接着往四周找下一个字母。
走到这里，字典树的这个节点挂着结束标记，意味着路径上的字母刚好拼成了目标单词 "pea"！把它收进答案。为了不重复收录，把这个单词从字典树上摘掉。
从这里往这个方向探一步，字母是 e。字典树里当前节点没有 e 这条分支，说明 "peae" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
从这里往这个方向探一步，字母是 t。字典树里当前节点没有 t 这条分支，说明 "pet" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
从这里往这个方向探一步，字母是 a。字典树里当前节点没有 a 这条分支，说明 "pa" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
格子的字母 e 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "pe"，沿着它接着往四周找下一个字母。
格子的字母 a 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "pea"，沿着它接着往四周找下一个字母。
从这里往这个方向探一步，字母是 e。字典树里当前节点没有 e 这条分支，说明 "peae" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
从这里往这个方向探一步，字母是 t。字典树里当前节点没有 t 这条分支，说明 "pet" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
从这里往这个方向探一步，字母是 a。字典树里当前节点没有 a 这条分支，说明 "pa" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
格子的字母 t 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "t"，沿着它接着往四周找下一个字母。
从这里往这个方向探一步，字母是 a。字典树里当前节点没有 a 这条分支，说明 "ta" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
格子的字母 e 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "te"，沿着它接着往四周找下一个字母。
从这里往这个方向探一步，字母是 p。字典树里当前节点没有 p 这条分支，说明 "tep" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
格子的字母 a 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "tea"，沿着它接着往四周找下一个字母。
走到这里，字典树的这个节点挂着结束标记，意味着路径上的字母刚好拼成了目标单词 "tea"！把它收进答案。为了不重复收录，把这个单词从字典树上摘掉。
从这里往这个方向探一步，字母是 e。字典树里当前节点没有 e 这条分支，说明 "teae" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
所有起点搜完，棋盘上能拼出的目标单词是 oat、pea、tea，一共 3 个，这就是最终答案。
三个高频追问：双指针同步、用 '#' 防重复用格、收词后摘标记去重。
参考代码
def findWords(board, words): trie = {} # 用嵌套字典当字典树 for w in words: node = trie for ch in w: node = node.setdefault(ch, {}) node['$'] = w # 结束标记存整词 R, C, res = len(board), len(board[0]), [] def dfs(r, c, node): ch = board[r][c] nxt = node.get(ch) if nxt is None: return # 无分支 → 剪枝 if '$' in nxt: res.append(nxt.pop('$')) # 收词并去重 board[r][c] = '#' # 标记已用 for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r+dr, c+dc if 0<=nr<R and 0<=nc<C and board[nr][nc] != '#': dfs(nr, nc, nxt) board[r][c] = ch # 回溯还原 for r in range(R): for c in range(C): dfs(r, c, trie) return res复杂度
- 时间：O(M·4·3^(L-1))，M 个起点格子，每条路径最多 4 个方向、深度为最长单词长 L；字典树把不可能的前缀提前剪掉，实际远小于此上界
- 空间：O(N)，N 是所有单词的总字母数，字典树最多存这么多节点；递归栈深度为最长单词长度 L
易错点
面试追问把动画讲成自己的话
追问DFS 时棋盘指针和字典树指针是什么关系？
追问怎么避免同一个格子在一个单词里被重复使用？
追问找到一个单词后为什么要把它从字典树上摘掉？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题