算法双杀：Trie（前缀树）实现 + 全排列（回溯经典）| 面试必刷模板题

目录一、Trie前缀树字符串查询的效率神器什么是前缀树核心设计完整实现代码关键解析二、全排列回溯算法入门经典题目描述核心思路回溯法完整实现代码关键解析三、两道题核心考点对比总结一、Trie前缀树字符串查询的效率神器什么是前缀树Trie 是一种专门用于处理字符串前缀匹配的数据结构核心优势是插入、查询单词 / 前缀的时间复杂度均为 O (L)L 为字符串长度比哈希表更适合高频前缀查询场景常用于实现自动补全、拼写检查、敏感词过滤等功能核心设计每个 Trie 节点包含children[26]子节点数组对应 26 个小写英文字母isEnd标记是否为单词的结束节点完整实现代码java运行class Trie { // Trie 节点定义 private static class TrieNode { TrieNode[] children; boolean isEnd; public TrieNode() { children new TrieNode[26]; isEnd false; } } private final TrieNode root; public Trie() { root new TrieNode(); } // 插入单词 public void insert(String word) { TrieNode node root; for (char c : word.toCharArray()) { int idx c - a; // 子节点不存在则创建 if (node.children[idx] null) { node.children[idx] new TrieNode(); } node node.children[idx]; } // 标记单词结束 node.isEnd true; } // 查询单词是否存在 public boolean search(String word) { TrieNode node root; for (char c : word.toCharArray()) { int idx c - a; if (node.children[idx] null) { return false; } node node.children[idx]; } // 必须是结束节点才算完整单词 return node.isEnd; } // 查询是否存在以 prefix 为前缀的单词 public boolean startsWith(String prefix) { TrieNode node root; for (char c : prefix.toCharArray()) { int idx c - a; if (node.children[idx] null) { return false; } node node.children[idx]; } // 只要前缀存在即可无需判断 isEnd return true; } }关键解析插入流程从根节点出发逐个字符向下遍历不存在的字符则创建新节点最后标记结束节点查询流程与插入类似逐个字符匹配中途不存在则返回 false查询单词需额外判断isEnd前缀查询与单词查询逻辑一致无需判断isEnd只要前缀路径存在即可二、全排列回溯算法入门经典题目描述给定一个不含重复数字的数组nums返回其所有可能的全排列。你可以按任意顺序返回答案。核心思路回溯法全排列的本质是枚举所有可能的排列组合回溯法是解决这类问题的标准方法选择每次选择一个未被使用的数字加入当前排列递归继续选择下一个数字直到排列长度等于数组长度回溯递归结束后撤销上一步的选择尝试其他可能完整实现代码java运行import java.util.ArrayList; import java.util.List; class Solution { public ListListInteger permute(int[] nums) { ListListInteger res new ArrayList(); ListInteger path new ArrayList(); boolean[] used new boolean[nums.length]; // 标记数字是否被使用 backtrack(nums, used, path, res); return res; } private void backtrack(int[] nums, boolean[] used, ListInteger path, ListListInteger res) { // 递归终止条件排列长度等于数组长度 if (path.size() nums.length) { res.add(new ArrayList(path)); // 拷贝当前路径避免后续修改影响结果 return; } // 遍历所有数字尝试选择未被使用的数字 for (int i 0; i nums.length; i) { if (used[i]) continue; // 跳过已使用的数字 // 选择 used[i] true; path.add(nums[i]); // 递归 backtrack(nums, used, path, res); // 回溯撤销选择 path.remove(path.size() - 1); used[i] false; } } }关键解析used 数组避免重复选择数字确保每个数字在排列中只出现一次路径拷贝递归终止时需要将当前路径的拷贝加入结果集否则后续回溯会修改路径内容回溯操作递归返回后撤销上一步的选择移除路径末尾元素、标记数字为未使用实现 “试错”三、两道题核心考点对比表格题目核心算法关键技巧适用场景Trie前缀树自定义数据结构 遍历节点设计、前缀匹配逻辑字符串高频查询、前缀匹配全排列回溯算法选择 / 递归 / 回溯、状态标记枚举所有可能组合、排列组合问题总结这两道题分别代表了数据结构和算法的两个经典方向Trie 让你掌握字符串高效查询的实现思路是处理字符串问题的利器全排列让你理解回溯算法的核心思想是解决排列组合问题的通用模板