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

目录

一、Trie（前缀树）：字符串查询的效率神器

什么是前缀树？

核心设计

完整实现代码

关键解析

二、全排列：回溯算法入门经典

题目描述

核心思路（回溯法）

完整实现代码

关键解析

三、两道题核心考点对比

总结

一、Trie（前缀树）：字符串查询的效率神器

什么是前缀树？

Trie 是一种专门用于处理字符串前缀匹配的数据结构，核心优势是：

• 插入、查询单词 / 前缀的时间复杂度均为 O (L)（L 为字符串长度），比哈希表更适合高频前缀查询场景
• 常用于实现自动补全、拼写检查、敏感词过滤等功能

核心设计

每个 Trie 节点包含：

1. children[26]：子节点数组（对应 26 个小写英文字母）
2. 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; } }

关键解析

1. 插入流程：从根节点出发，逐个字符向下遍历，不存在的字符则创建新节点，最后标记结束节点
2. 查询流程：与插入类似，逐个字符匹配，中途不存在则返回 false，查询单词需额外判断isEnd
3. 前缀查询：与单词查询逻辑一致，无需判断isEnd，只要前缀路径存在即可

二、全排列：回溯算法入门经典

题目描述

给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

核心思路（回溯法）

全排列的本质是枚举所有可能的排列组合，回溯法是解决这类问题的标准方法：

1. 选择：每次选择一个未被使用的数字，加入当前排列
2. 递归：继续选择下一个数字，直到排列长度等于数组长度
3. 回溯：递归结束后，撤销上一步的选择，尝试其他可能

完整实现代码

java

运行

import java.util.ArrayList; import java.util.List; class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); boolean[] used = new boolean[nums.length]; // 标记数字是否被使用 backtrack(nums, used, path, res); return res; } private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> 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; } } }

关键解析

1. used 数组：避免重复选择数字，确保每个数字在排列中只出现一次
2. 路径拷贝：递归终止时，需要将当前路径的拷贝加入结果集，否则后续回溯会修改路径内容
3. 回溯操作：递归返回后，撤销上一步的选择（移除路径末尾元素、标记数字为未使用），实现 “试错”

三、两道题核心考点对比

表格

总结

这两道题分别代表了数据结构和算法的两个经典方向：

• Trie 让你掌握字符串高效查询的实现思路，是处理字符串问题的利器
• 全排列让你理解回溯算法的核心思想，是解决排列组合问题的通用模板