单词搜索 Ii

212. 单词搜索 II

问题重述

给定一个 m x n 二维字符网格 board 和一个由字符串组成的列表 words。请你找出所有可以由网格中的字母构成的单词，并以列表形式返回。

规则和 "单词搜索 I" 完全相同：

1. 单词必须按照字母顺序，通过相邻的单元格内的字母构成。

2. “相邻”指水平或垂直相邻。

3. 同一个单元格内的字母在同一个单词中不能被重复使用。

示例: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]] words = ["oath","pea","eat","rain"] 输出: ["eat","oath"]

---

问题分析与思路演进

思路一：暴力法 (最容易想到的方法)

我们已经会做 "单词搜索 I" 了，不是吗？那最简单的想法就是，对 words 列表里的每一个单词，都单独在 board 上跑一遍 "单词搜索 I" 的 exist 算法。

代码思路:

// 伪代码
List<String> findWords(board, words) {
    List<String> result = new ArrayList<>();
    for (String word : words) {
        if (exist(board, word)) { // exist 是上一题的解法
            result.add(word);
        }
    }
    return result;
}

复杂度分析与问题所在: 假设 words 列表里有 k 个单词，平均长度为 L，board 大小为 M x N。 "单词搜索 I" 的复杂度约是 O(M * N * 4^L)。 那么，总复杂度就是 O(k * M * N * 4^L)。 这是一个非常恐怖的数字！当 words 列表很大时，这个方法一定会超时。

核心问题在哪？ —— 重复搜索！ 比如 words 里有 "apple", "apply", "app"。我们在搜索 "apple" 的时候，会走 a -> p -> p 这条路径；搜索 "apply" 时，又会重新走一遍 a -> p -> p；搜索 "app" 时，还是会走 a -> p -> p。我们把大量的计算资源浪费在了重复搜索公共前缀上。

怎么解决这个问题？我们需要一种方法，能够同时搜索所有的单词，而不是一个一个地搜。

思路二：终极优化 (DFS + 前缀树)

当遇到大量字符串、需要处理公共前缀问题时，我们的脑海里必须立刻闪现出一个神器——前缀树（Trie），也叫字典树。

前缀树是什么？ 它是一种专门用于快速检索字符串集合的树形结构。

• 每个节点代表一个字符。

• 从根节点到任意一个节点的路径，构成了一个字符串前缀。

• 在代表单词结尾的节点上，我们可以做一个标记（比如存下这个单词本身）。

如何用前缀树优化？

1. 预处理: 首先，我们把 words 列表里的所有单词，全部插入到一棵前缀树里。这相当于我们建立了一本高效的“字典”。

2. 统一搜索: 接下来，我们不再是为每个单词进行一次独立的 DFS，而是对 board 的每个单元格 (i, j) 只进行一次 DFS。

3. DFS 与前缀树联动:

   • DFS 从 board[i][j] 开始，同时，我们在前缀树中也从 root 节点开始。

   • 当 DFS 从 (i, j) 移动到一个相邻的单元格 (i', j') 时，比如 board[i'][j'] 的字符是 c，我们就在前缀树中，从当前节点移动到其代表字符 c 的子节点。

   • 强大的剪枝: 如果在 DFS 的某一步，发现当前路径在前缀树中走不下去了（比如，前缀树的当前节点没有对应下一个字符的子节点），说明 board 上的这条路径不可能构成我们字典里的任何一个单词！我们就可以立即停止对这条路径的深入探索，直接回溯。这就是前缀树带来的巨大性能提升！

   • 找到单词: 如果在 DFS 的过程中，我们走到了前缀树中的一个节点，并且这个节点标记为一个单词的结尾，那么恭喜，我们找到了一个答案！把它加入结果集。

一个重要的优化: 找到了一个单词（比如 "oath"）之后，为了防止在棋盘的其他地方再次找到它而重复添加，我们应该如何处理？

• 方法一：用一个 Set 来保存结果，自动去重。

• 方法二（更巧妙）：当我们找到 "oath" 并加入结果后，可以把前缀树上代表 "oath" 结尾的那个节点的单词标记清除（比如 node.word = null）。这样，即使以后再次走到这个节点，也不会重复添加了。这是一种非常聪明的技巧，能顺便剪掉一些不必要的搜索。

Java 代码实现 (DFS + 前缀树)

class Solution {
​
    // 1. 定义前缀树节点
    class TrieNode {
        TrieNode[] children;
        String word; // 在单词的结尾节点上，存储整个单词
​
        public TrieNode() {
            this.children = new TrieNode[26]; // 对应 'a' 到 'z'
            this.word = null;
        }
    }
​
    // 2. 构建前缀树
    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode curr = root;
            for (char c : w.toCharArray()) {
                int index = c - 'a';
                if (curr.children[index] == null) {
                    curr.children[index] = new TrieNode();
                }
                curr = curr.children[index];
            }
            curr.word = w; // 将单词存放在结尾节点
        }
        return root;
    }
​
    /**
     * LeetCode 212: 单词搜索 II
     *
     * @param board 二维字符网格
     * @param words 单词列表
     * @return 所有在网格中找到的单词
     */
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        if (board == null || board.length == 0 || board[0].length == 0 || words == null || words.length == 0) {
            return result;
        }
​
        // 步骤一：构建前缀树
        TrieNode root = buildTrie(words);
​
        int rows = board.length;
        int cols = board[0].length;
​
        // 步骤二：遍历网格，以每个单元格为起点进行 DFS
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(board, i, j, root, result);
            }
        }
​
        return result;
    }
​
    /**
     * 深度优先搜索
     * @param board    网格
     * @param r        当前行
     * @param c        当前列
     * @param parent   当前在前缀树中的父节点
     * @param result   结果集
     */
    private void dfs(char[][] board, int r, int c, TrieNode parent, List<String> result) {
        // --- 剪枝与越界检查 ---
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
            return;
        }
        char ch = board[r][c];
        // 如果当前格子被访问过 (标记为'#')，或者在前缀树中没有对应路径，则剪枝
        if (ch == '#' || parent.children[ch - 'a'] == null) {
            return;
        }
​
        // --- 核心逻辑 ---
        // 移动到前缀树的下一个节点
        TrieNode curr = parent.children[ch - 'a'];
​
        // 检查是否找到了一个单词
        if (curr.word != null) {
            result.add(curr.word);
            // 找到了就将其从前缀树中“删除”（清空标记），防止重复添加
            curr.word = null;
        }
​
        // 做出选择：标记当前单元格已访问
        board[r][c] = '#';
​
        // 探索：向四个方向递归
        dfs(board, r + 1, c, curr, result);
        dfs(board, r - 1, c, curr, result);
        dfs(board, r, c + 1, curr, result);
        dfs(board, r, c - 1, curr, result);
​
        // 撤销选择 (回溯)：恢复现场
        board[r][c] = ch;

        // 剪枝：如果一个TrieNode的子节点都被访问完了（word被置null），这个TrieNode也就没用了，可以优化删除，但通常不这么做，因为逻辑复杂且提升有限。
    }
}

关键概念与技术解释

1. 前缀树 (Trie / Prefix Tree):

   • 核心优势: 高效地存储和查询一个字符串集合。它的查询时间复杂度只跟查询字符串的长度 L 有关，而跟字典里单词的数量 K 无关。

   • 在本题的应用: 它将 K 次独立的、低效的搜索，整合为了一次统一的、高效的搜索。它充当了一个“导航地图”，在 DFS 探索 board 的同时，告诉我们当前的路径是否“有前途”（即是否是字典中某个单词的前缀）。

2. DFS + 回溯:

   • 这依然是解决迷宫/路径搜索问题的基础框架。

   • DFS 负责深度探索所有可能的路径。

   • 回溯（恢复现场，board[r][c] = ch）保证了从不同起点出发的搜索路径不会相互干扰。

3. 剪枝 (Pruning):

   • 这是算法优化的灵魂。本解法中的剪枝体现在两个层面：

     • 前缀剪枝: 如果当前 board 上的路径在前缀树中找不到对应的节点，说明这个方向不可能构成任何目标单词，立即停止深入，这是最核心的剪枝。

     • 结果去重剪枝: 找到一个单词后，通过 curr.word = null 将其从前缀树中逻辑删除，这不仅避免了结果重复，也可能让后续的搜索提前结束（如果 curr 节点没有其他子节点了）。