每日算法 — 使用java实现单词搜索：Trie前缀树与回溯剪枝搜索

单词搜索（Word Search）是一款风靡全球的益智文字游戏：玩家在字母组成的二维网格中，找出隐藏在其中的若干单词。规则看似简单——单词可沿上下左右四个方向延伸，且每个格子只能使用一次——但要在海量字母中快速定位所有目标单词，背后需要高效的字符串检索与路径搜索算法协同工作。本文将用Java实现一个带Trie前缀树加速的单词搜索求解器，讲解如何通过前缀匹配大幅剪枝无效搜索分支，并给出完整可运行的代码与复杂度分析。

一、问题建模与算法选型

将单词搜索抽象为图论问题：网格中的每个字母是一个节点，相邻（上下左右）节点之间有边相连。寻找单词的过程等价于在图中寻找一条路径，使得路径上节点的字符依次拼接等于目标单词。

朴素方案是对每个单词分别执行一次DFS，时间复杂度为 O(N * M * 4^L)，其中 N*M 为网格大小，L 为单词长度。当单词数量很多时，这种方案会产生大量重复的前缀遍历。

核心优化思路——Trie前缀树：
– 将所有目标单词预先插入Trie树，共享公共前缀节点
– DFS时实时检查当前路径前缀是否存在于Trie中，若不存在则立即剪枝
– 当走到Trie的单词终止节点时，记录找到一个单词，并可继续搜索（允许单词之间共享前缀）

这种”多模式串同时匹配”的策略将时间复杂度从线性增长于单词数量，降低到接近于单次深度优先搜索的开销。

二、Trie前缀树数据结构

Trie树（又称前缀树）是一种有序树状数据结构，用于存储关联数组，其键通常是字符串。每个节点代表一个字符，从根到某节点的路径上的字符序列即为该节点对应的前缀。

import java.util.*;

/**
 * Trie前缀树节点
 * 每个节点包含：子节点映射、是否为单词结尾标记、到达该节点的完整单词（用于快速收集结果）
 */
class TrieNode {
    // 子节点：字符 -> TrieNode，使用HashMap实现O(1)查找
    Map<Character, TrieNode> children;
    // 标记：从根到该节点是否构成一个完整单词
    boolean isEndOfWord;
    // 当isEndOfWord为true时，存储完整的单词字符串（避免回溯时重新拼接）
    String word;

    TrieNode() {
        this.children = new HashMap<>();
        this.isEndOfWord = false;
        this.word = null;
    }
}

/**
 * Trie前缀树
 * 提供插入单词和查询前缀的功能
 */
class Trie {
    private final TrieNode root;

    Trie() {
        this.root = new TrieNode();
    }

    /**
     * 将单词插入Trie树
     * 时间复杂度：O(L)，L为单词长度
     */
    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            // 若当前字符分支不存在，则创建新节点
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
        }
        node.isEndOfWord = true;
        node.word = word;  // 在终止节点记录完整单词
    }

    /**
     * 获取根节点，用于DFS时从根开始匹配
     */
    TrieNode getRoot() {
        return root;
    }
}

三、回溯搜索与剪枝策略

从网格的每个格子出发，沿着Trie树的边进行深度优先搜索。核心剪枝规则如下：

1. 边界剪枝：行或列越界时停止
2. 访问剪枝：每个格子只能使用一次，用标记数组记录已访问格子
3. 前缀剪枝：当前路径的下一个字符不在Trie当前节点的子节点中时，立即停止该分支
4. 单词收集：到达Trie终止节点时，记录单词并从字典中移除（防止重复收集同一单词）

/**
 * 单词搜索求解器
 * 基于Trie前缀树 + DFS回溯 + 多路剪枝
 */
public class WordSearchSolver {
    private final char[][] board;
    private final int rows;
    private final int cols;
    private final Trie trie;
    private final List<String> foundWords;
    // 四个方向：上、下、左、右
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public WordSearchSolver(char[][] board, String[] words) {
        this.board = board;
        this.rows = board.length;
        this.cols = board[0].length;
        this.trie = new Trie();
        this.foundWords = new ArrayList<>();
        // 将所有目标单词插入Trie
        for (String word : words) {
            trie.insert(word);
        }
    }

    /**
     * 主入口：搜索网格中所有存在于字典中的单词
     * 返回找到的单词列表
     */
    public List<String> findAllWords() {
        // 从每个格子出发尝试DFS
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                boolean[][] visited = new boolean[rows][cols];
                dfs(i, j, trie.getRoot(), visited);
            }
        }
        return foundWords;
    }

    /**
     * 深度优先搜索
     * @param r 当前行
     * @param c 当前列
     * @param node Trie中当前匹配到的节点
     * @param visited 访问标记数组
     */
    private void dfs(int r, int c, TrieNode node, boolean[][] visited) {
        // 剪枝1：边界检查
        if (r < 0 || r >= rows || c < 0 || c >= cols) {
            return;
        }
        // 剪枝2：已访问检查
        if (visited[r][c]) {
            return;
        }

        char ch = board[r][c];
        // 剪枝3：前缀不存在于Trie中
        TrieNode nextNode = node.children.get(ch);
        if (nextNode == null) {
            return;
        }

        // 标记当前格子为已访问
        visited[r][c] = true;

        // 若到达Trie终止节点，找到一个单词
        if (nextNode.isEndOfWord) {
            foundWords.add(nextNode.word);
            // 去重：将终止标记置为false，避免同一单词被多次记录
            // 注意：不删除节点，因为该前缀可能还是其他更长单词的前缀
            nextNode.isEndOfWord = false;
        }

        // 向四个方向继续搜索
        for (int[] dir : DIRECTIONS) {
            int nr = r + dir[0];
            int nc = c + dir[1];
            dfs(nr, nc, nextNode, visited);
        }

        // 回溯：恢复访问标记，供其他路径使用
        visited[r][c] = false;
    }
}

四、进阶优化：Trie剪枝与字典去重

上述实现已能高效工作，但面对极大规模输入时仍有优化空间：

1. 提前移除无分支节点（Trie压缩）

当某个单词被找到后，若其终止节点不再有子节点，则可以沿路径向上删除这些无用节点。这能进一步减少Trie的规模，加速后续搜索的get操作。

/**
 * 从Trie中移除已找到的单词，同时清理无用节点
 * @param node 当前节点
 * @param word 要移除的单词
 * @param depth 当前深度
 * @return 若当前子树已为空则返回true，否则返回false
 */
private boolean remove(TrieNode node, String word, int depth) {
    if (depth == word.length()) {
        // 到达终止节点
        if (!node.isEndOfWord) {
            return false;  // 单词不存在
        }
        node.isEndOfWord = false;
        node.word = null;
        // 若该节点无子节点，则可以删除
        return node.children.isEmpty();
    }

    char ch = word.charAt(depth);
    TrieNode child = node.children.get(ch);
    if (child == null) {
        return false;
    }

    boolean shouldDeleteChild = remove(child, word, depth + 1);
    if (shouldDeleteChild) {
        node.children.remove(ch);
        // 若当前节点也不是终止节点且无其他子节点，则也可以删除
        return !node.isEndOfWord && node.children.isEmpty();
    }
    return false;
}

2. 网格字符频率预过滤

在构建Trie前，先统计网格中各字符的出现次数。若某单词包含网格中不存在的字符，或其字符出现次数超过网格中的可用次数，则直接排除，避免插入Trie。

/**
 * 预过滤：根据网格字符频率筛除不可能存在的单词
 */
private String[] prefilterWords(String[] words, char[][] board) {
    // 统计网格字符频率
    Map<Character, Integer> boardFreq = new HashMap<>();
    for (char[] row : board) {
        for (char c : row) {
            boardFreq.merge(c, 1, Integer::sum);
        }
    }

    List<String> filtered = new ArrayList<>();
    for (String word : words) {
        Map<Character, Integer> wordFreq = new HashMap<>();
        for (char c : word.toCharArray()) {
            wordFreq.merge(c, 1, Integer::sum);
        }
        boolean possible = true;
        for (Map.Entry<Character, Integer> entry : wordFreq.entrySet()) {
            if (boardFreq.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                possible = false;
                break;
            }
        }
        if (possible) {
            filtered.add(word);
        }
    }
    return filtered.toArray(new String[0]);
}

五、完整运行示例

以下是一个包含主函数的完整可运行示例，演示如何在字母网格中搜索多个单词：

public class Main {
    public static void main(String[] args) {
        // 定义字母网格
        char[][] board = {
            {'o', 'a', 'a', 'n'},
            {'e', 't', 'a', 'e'},
            {'i', 'h', 'k', 'r'},
            {'i', 'f', 'l', 'v'}
        };

        // 目标单词列表
        String[] words = {"oath", "pea", "eat", "rain", "oathk", "hkl"};

        WordSearchSolver solver = new WordSearchSolver(board, words);
        List<String> result = solver.findAllWords();

        System.out.println("找到的单词：" + result);
        // 预期输出：找到的单词：[oath, eat, hkl, oathk]
        // 说明：
        // - "oath": (0,0)->(1,1)->(1,2)->(2,2) 即 o->t->a->h
        // - "eat": (1,2)->(0,2)->(1,1) 或 (1,2)->(2,2)->(1,1) 即 e->a->t
        // - "hkl": (2,1)->(2,2)->(2,3) 即 h->k->l
        // - "oathk": (0,0)->(1,1)->(1,2)->(2,2)->(2,1) 即 o->t->a->h->k
    }
}

六、复杂度分析

其中Trie的空间复杂度为所有目标单词的字符总数（共享前缀时会更小）。在实际运行中，前缀剪枝能将搜索空间压缩数个数量级，尤其是当目标单词有大量公共前缀时效果最为显著。

七、总结与延伸

本文通过Java实现了单词搜索游戏的高效求解器，核心要点包括：

• Trie前缀树作为多模式串的共享索引结构，将单词匹配从”逐词线性扫描”升级为”前缀驱动的联合搜索”
• DFS回溯配合访问标记数组，确保每个格子只被使用一次，天然满足游戏规则
• 三级剪枝（边界、访问状态、前缀不存在）层层过滤无效分支，是算法效率的关键
• Trie节点删除与字符频率预过滤作为进阶优化，适用于超大规模输入场景

延伸方向包括：将DFS改为非递归实现以降低栈深度风险、引入双向BFS处理超长单词、使用A*启发式搜索优先探索更有希望的分支，以及将算法扩展到三维字母立方体或允许斜向移动的变体规则中。