单词搜索 II 图解题解

这道题到底在问什么

网格

oaan / etae / ihkr / iflv（4×4）

单词

words = [oath, pea, eat, rain]

输出

[oath, eat]

最优解：一步一步想明白

1. 3最直接的想法：对 words 里每个单词，都从网格各处单独做一遍 DFS。可单词之间往往共享前缀，比如 oath 和 oak 都以 o-a 开头，这段路你会一搜再搜，白白重复。
2. 4换个思路：先把所有单词塞进一棵字典树 Trie，共享的前缀就只存一份。然后网格只 DFS 一遍，手里攥着 Trie 的当前节点同步往下走。当前格的字母在 Trie 里没有分支，就立刻剪掉，连试都不试。
3. 5oath / pea / eat / rain 共四条路径，公共前缀只存一份先把四个单词建成这棵 Trie。从根往右每走一条边添一个字母，带勾的节点表示一个单词到此结束。接下来网格 DFS 时，我手里会一直攥着 Trie 上的一个节点，走到哪个字母就往那条边下沉。
4. 6当前格 (0,0)=o；Trie：根 → o，前缀 o 存在，继续外层双循环让每个格子都当一次起点。先从左上角 (0,0)=o 出发。看 Trie 根：有没有 o 这条边？有。于是攥住 o 节点，把 (0,0) 标成走过，继续往四周探。
5. 7(0,0) 已占用(橙黄)；当前格 (0,1)=a；Trie：o → a，前缀 oa 存在进入 (0,0) 后先把它原地改成星号占住，这样这条路径上不会重复用它。再看四个方向，右边 (0,1)=a。问当前 Trie 节点 o：有 a 这条边吗？有。攥住 a 节点，推进到 (0,1)，路径变成 o-a。
6. 8路径占住 (0,0)(0,1)；当前格 (1,1)=t；Trie：a → t，前缀 oat 存在在 (0,1)=a 处把它也占住，看四周。下方 (1,1)=t。当前 Trie 节点 a 有没有 t 边？有。推进到 (1,1)，路径变成 o-a-t。递归栈现在压了三层，每层都记着自己攥的 Trie 节点。
7. 9路径占住 (0,0)(0,1)(1,1)；当前格 (2,1)=h；Trie：t → h✓，单词 oath 结束 → 收下在 (1,1)=t 处往下走到 (2,1)=h。当前 Trie 节点 t 有 h 边，而且这个 h 节点带勾——表示单词 oath 在此结束。立刻把 oath 收进答案，并把这个勾摘掉防止重复收。已找到单词 +1。
8. 10h 之后无分支 → 逐层返回；每返回一层就把星号改回原字母oath 之后的 h 节点没有更多分支，这条路探到头。于是逐层返回，每弹出一层就把那一格的星号改回原来的字母——这就是回溯，把网格恢复原样，好让别的起点重新使用这些格子。
9. 11当前格 (0,3)=n；Trie 根的边只有 o/p/e/r，没有 n → 直接剪掉，连邻居都不看这就是 Trie 剪枝的威力。轮到 (0,3)=n 当起点，问 Trie 根有没有 n 边？根的边只有 o、p、e、r，没有 n。于是这一格直接红牌返回，连它的四个邻居都不去看——所有以 n 开头的死路一刀全砍掉。
10. 12当前格 (1,3)=e；Trie：根 → e，前缀 e 存在，开始找 eat继续换起点。到 (1,3)=e，Trie 根有 e 边，攥住 e 节点。注意左上那个 e 在 (1,0)，它的邻居里没有 a，走不通；而 (1,3) 这个 e 右边和下边能接上 a-t，所以 eat 是从这里连出来的。
11. 13(1,3) 占住；当前格 (1,2)=a；Trie：e → a，前缀 ea 存在从 (1,3)=e 往左到 (1,2)=a。当前 Trie 节点 e 有 a 边，推进，路径 e-a。两格都被星号占住，递归栈两层。
12. 14(1,3)(1,2) 占住；当前格 (1,1)=t；Trie：a → t✓，单词 eat 结束 → 收下从 (1,2)=a 往左到 (1,1)=t。当前 Trie 节点 a 有 t 边，且这个 t 带勾——单词 eat 结束！收下 eat，摘掉勾。已找到单词 +1，现在是 2 个：oath 和 eat。
13. 15网格已全部还原；答案 = [oath, eat]；pea、rain 全程没命中继续把剩下的起点跑完。pea 因为网格里没有 p，rain 因为根没接上完整路径，都没命中。所有 DFS 回溯后网格恢复原样，最终答案就是高亮的两条路径连出的 oath 和 eat。
14. 18一句话记住：把单词建成 Trie，网格 DFS 时手里同步攥着 Trie 节点往下走，当前字母在 Trie 里没分支就立刻剪掉，命中带词节点就收下并摘标记。
15. 20若邻居只判越界：在 (1,2)=a 又把右邻 (1,3) 当新格走回去，路径凭空多出字母 → 连出假单词演示这个坑：搜 eat 时走到 (1,2)=a，如果邻居判断忘了排除星号，就会从 (1,2) 又跳回刚占住的 (1,3)=e。同一个 e 被用了两次，等于在网格里凭空造字母，可能连出根本不存在的单词。所以邻居必须同时不越界且不是星号。
16. 28这题学完别乱跳，去专题 /leetcode-animation/ds?k=trie 连刷同类题：先打牢 LC208 实现 Trie，再回看 LC79 单词搜索 I 体会单串 DFS，最后回到本题感受 Trie 批量剪枝的提速。卡住时问 AI 助教「我的 DFS 为什么没剪枝」。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def findWords(self, board, words):
        trie = {}
        for w in words:                 # 1. 建 Trie
            cur = trie
            for ch in w:
                cur = cur.setdefault(ch, {})
            cur["#"] = w            # 单词末尾打标记
        rows, cols = len(board), len(board[0])
        ans = []
        def dfs(r, c, node):
            ch = board[r][c]
            if ch not in node:          # 2. Trie 剪枝
                return
            nxt = node[ch]
            word = nxt.pop("#", None)   # 命中就摘标记防重复
            if word:
                ans.append(word)
            board[r][c] = "*"           # 占住当前格
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "*":
                    dfs(nr, nc, nxt)        # 带着子节点往下走
            board[r][c] = ch            # 3. 回溯还原
        for r in range(rows):
            for c in range(cols):
                dfs(r, c, trie)
        return ans

struct Trie {
    unordered_map<char, Trie*> child;
    string word;
};
class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie* root = new Trie();
        for (auto& w : words) {                 // 1. 建 Trie
            Trie* cur = root;
            for (char ch : w) {
                if (!cur->child[ch]) cur->child[ch] = new Trie();
                cur = cur->child[ch];
            }
            cur->word = w;
        }
        vector<string> ans;
        int m = board.size(), n = board[0].size();
        function<void(int,int,Trie*)> dfs = [&](int r, int c, Trie* node) {
            char ch = board[r][c];
            if (!node->child.count(ch)) return;     // 2. Trie 剪枝
            Trie* nxt = node->child[ch];
            if (!nxt->word.empty()) { ans.push_back(nxt->word); nxt->word.clear(); }
            board[r][c] = '*';                      // 占住当前格
            int dirs[5] = {1,0,-1,0,1};
            for (int k=0;k<4;k++) {
                int nr=r+dirs[k], nc=c+dirs[k+1];
                if (nr>=0 && nr<m && nc>=0 && nc<n && board[nr][nc] != '*') dfs(nr,nc,nxt);
            }
            board[r][c] = ch;                       // 3. 回溯还原
        };
        for (int r=0;r<m;r++) for (int c=0;c<n;c++) dfs(r,c,root);
        return ans;
    }
};

class Solution {
    static class Trie {
        Map<Character, Trie> child = new HashMap<>();
        String word;
    }
    public List<String> findWords(char[][] board, String[] words) {
        Trie root = new Trie();
        for (String w : words) {                 // 1. 建 Trie
            Trie cur = root;
            for (char ch : w.toCharArray()) cur = cur.child.computeIfAbsent(ch, k -> new Trie());
            cur.word = w;
        }
        List<String> ans = new ArrayList<>();
        for (int r=0;r<board.length;r++) for (int c=0;c<board[0].length;c++) dfs(board,r,c,root,ans);
        return ans;
    }
    private void dfs(char[][] board, int r, int c, Trie node, List<String> ans) {
        char ch = board[r][c];
        Trie nxt = node.child.get(ch);
        if (nxt == null) return;                  // 2. Trie 剪枝
        if (nxt.word != null) { ans.add(nxt.word); nxt.word = null; }
        board[r][c] = '*';                        // 占住当前格
        int[] d = {1,0,-1,0,1};
        for (int k=0;k<4;k++) {
            int nr=r+d[k], nc=c+d[k+1];
            if (nr>=0 && nr<board.length && nc>=0 && nc<board[0].length && board[nr][nc] != '*') dfs(board,nr,nc,nxt,ans);
        }
        board[r][c] = ch;                         // 3. 回溯还原
    }
}

# 模板：一批模式串 在 网格/序列 上批量匹配
# 1) 建 Trie：把所有模式串塞进去，末节点打词标记
trie = {}
for w in words:
    node = trie
    for ch in w: node = node.setdefault(ch, {})
    node['#'] = w
# 2) DFS：第三个参数始终是 当前 Trie 节点
def dfs(r, c, node):
    ch = board[r][c]
    if ch not in node: return          # 剪枝：无分支即停
    nxt = node[ch]
    if w := nxt.pop('#', None): ans.append(w)   # 命中并摘标记
    board[r][c] = '*'                  # 占位
    for nr, nc in neighbors(r, c):
        if in_bound(nr, nc) and board[nr][nc] != '*': dfs(nr, nc, nxt)
    board[r][c] = ch                   # 回溯还原

// 1) 建 Trie：unordered_map<char,Trie*> child; string word;
// 2) DFS 第三参数 = 当前 Trie 节点
void dfs(int r, int c, Trie* node) {
    char ch = board[r][c];
    if (!node->child.count(ch)) return;        // 剪枝
    Trie* nxt = node->child[ch];
    if (!nxt->word.empty()) { ans.push_back(nxt->word); nxt->word.clear(); }  // 命中并摘
    board[r][c] = '*';                         // 占位
    for (auto [nr,nc] : neighbors(r,c))
        if (inBound(nr,nc) && board[nr][nc] != '*') dfs(nr,nc,nxt);
    board[r][c] = ch;                          // 回溯
}

// 1) 建 Trie：Map<Character,Trie> child; String word;
// 2) DFS 第三参数 = 当前 Trie 节点
void dfs(int r, int c, Trie node) {
    char ch = board[r][c];
    Trie nxt = node.child.get(ch);
    if (nxt == null) return;                   // 剪枝
    if (nxt.word != null) { ans.add(nxt.word); nxt.word = null; }  // 命中并摘
    board[r][c] = '*';                         // 占位
    for (int[] nb : neighbors(r, c))
        if (inBound(nb) && board[nb[0]][nb[1]] != '*') dfs(nb[0], nb[1], nxt);
    board[r][c] = ch;                          // 回溯

复杂度

面试官可能追问