一、前缀树基础知识
1. 前缀树概念
前缀树，又称为字典树，它用一个树状的数据结构存储一个字典中的所有单词。如果一个字典中包含弹词 can、cat、come、do、i、in 和 inn，那么保存该字典所有单词的前缀树如图 9.1 所示。
前缀树是一棵多叉树，一个节点可能有多个子节点。前缀树中除根节点外，每个节点表示字符串中的一个字符，而字符串由前缀树的路径表示。前缀树的根节点不表示任何字符。例如，从图 9.1 中前缀树的根节点开始找到字符 c 对应的节点，接着经过字符 a 对应的节点到达字符 n 对应的节点，该路径表示字符串 can。
如果两个单词的前缀（即单词最开始的若干字符）相同，那么它们在前缀树中对应的路径的前面的节点是重叠的。例如，can 和 cat 的前两个字符相同，它们在前缀树对应的两条路径中最开始的 3 个节点（根节点、字符 c 和字符 a 对应的节点）重叠，它们共同的前缀之后的字符对应的节点一定是在最后一个共同节点的子树中。例如，can 和 cat 的共同前缀 ca 在前缀树中的最后一个节点是第 3 层的第 1 个节点，两个字符串共同的前缀之后的字符 n 和 t 都在最后一个公共节点的子树之中。
字符串在前缀树中的路径并不一定终止于叶节点。如果一个单词是另一个单词的前缀，那么较短的单词对应的路径是较长的单词对应的路径的一部分。例如，在图 9.1 中，字符串 in 对应的路径是字符串 inn 对应的路径的一部分。
如果前缀树路径到达某个节点时它表示了一个完整的字符串，那么字符串最后一个字符对应的节点有特殊的标识。例如，图 9.1 中字符串最后一个字符对应的节点都用灰色背景标识。从根节点出发到达表示字符'i'的节点，由于该节点被标识为字符串的最后一个字符，因此此时路径表示的字符串 i 是字典中的一个单词。接着往下到达表示字符 n 的节点，这个节点也被标识为字符串的最后一个字符，因此此时路径表示的字符串 in 是字典中的一个单词。接着往下到达另一个表示字符 n 的节点，该节点也有同样的标识，因此此时路径表示的字符串 inn 是字典中的另一个单词。
二、前缀树知识扩展
1. 前缀树基础
知识扩展
由于前缀树特殊的构造方式，需要像树节点一样构造一个用于支持其特性的类。以小写英语词语为例，构造一个前缀树节点，其子节点为大小 26 的前缀树节点，并且需要定义一个标识用于表示当前节点是否构成一个单词。定义前缀树节点如下：
/**
* 前缀树节点
* @author nepakina
*/
public class TrieNode {
TrieNode[] children;
boolean isEnd;
public TrieNode() {
isEnd = false;
children = new TrieNode[26];
}
}
题目练习
Ⅰ：实现前缀树
题目描述
请设计实现一棵前缀树 Trie，它有如下操作。
> 函数 insert，在前缀树中添加一个字符串。
> 函数 search，查找字符串。如果前缀树中包含该字符串，则返回 true；否则返回 false。
> 函数 startWith，查找字符串前缀。如果前缀树中包含以该前缀开头的字符串，则返回 true；否则返回 false。
题目分析
难度： ⭐🐇🐇🐇🐇
思路： 这是一个比较标准的前缀树搜索问题。
参考代码
/**
* 前缀树
*
* @author nepakina
*/
public class Trie {
private final TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
// 定义一个新的指针用于处理，保证 root 不变
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (cur.children[ch - 'a'] == null) {
cur.children[ch - 'a'] = new TrieNode();
}
cur = cur.children[ch - 'a'];
}
cur.isEnd = true;
}
public boolean search(String word) {
return findPrefixWorld(word, false);
}
public boolean startWith(String prefix) {
return findPrefixWorld(prefix, true);
}
/**
* 寻找前缀单词
*
* @param word 单词
* @param isPrefix 是否以前缀方式处理
* @return 结果
*/
private boolean findPrefixWorld(String word, boolean isPrefix) {
// 前缀和单词其区别仅仅是最后遍历到的节点是否标记为单词而已
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (cur.children[ch - 'a'] == null) {
return false;
}
cur = cur.children[ch - 'a'];
}
// 前缀时不需要考虑是否是单词
return isPrefix || cur.isEnd;
}
}
Tips：2025-05-30
2. 前缀树的应用
知识扩展
前缀树主要用来解决与字符串查找相关的问题。如果字符串的长度为 k ，由于在前缀树中查找一个字符串相当于顺着前缀树的路径查找字符串的每个字符，因此时间复杂度是 O(k)。
在哈希表中查找字符串的时间复杂度是 O(1)。但哈希表需要输入完整的字符串才能进行查找操作，随着完整字符串增多其内存开销也将极速增大，而前缀树可以很好的解决这个问题。例如，可以只输入字符串的前面若干字符，即前缀，查找以这个前缀开头的所有字符串。如果要求根据字符串的前缀进行查找，那么合理应用前缀树可能是解决这个问题的关键。
题目练习
Ⅰ：替换单词
题目描述
英语中有一个概念叫词根。在词根后面加上若干字符就能拼出更长的单词。例如，"an" 是一个词根，在它后面加上 "other" 就能得到另一个单词 "another"。现在给定一个由词根组成的字典和一个英语句子，如果句子中的单词在字典中有它的词根，则用它的词根替换该单词；如果单词没有词根，则保留该单词。请输出替换后的句子。例如，如果词根字典包含字符串 ["cat", "bat", "rat"]，英语句子为 "the cattle was rattled by the battery"，则替换之后的句子是 "the cat was rat by the bat"。
题目分析
难度： ⭐⭐🐇🐇🐇
思路： 利用单词字典找前缀的单词和找指定单词的前缀，其实本质都是前缀树的一种变形。这里可以将前缀作为字典，构建出字典树；然后在字典树中寻找单词，不同的时，此时的结束标准应该调整一下，更改为如果当前字符是前缀结束点，则用当前前缀结束点的这个前缀字符串代替原来的字符串返回；而如果后续节点已经是 null 的情况下，直接返回当前输入的字符串即可。
参考代码
/**
* 重新替换原有句子
*/
public String replaceWords(List<String> dict, String words) {
StringBuilder res = new StringBuilder();
String[] wordArr = words.split(" ");
TrieNode trieNode = buildDict(dict);
// 通过首个单词标识解决多空格问题
boolean isFirst = true;
for (int i = 0; i < wordArr.length; i++) {
// 也可以通过替换数组元素后使用拼接函数
// wordArr[i] = findReplaceWorld(trieNode, wordArr[i]);
if (isFirst) {
isFirst = false;
res.append(findReplaceWorld(trieNode, wordArr[i]));
} else {
res.append(" ").append(findReplaceWorld(trieNode, wordArr[i]));
}
}
// return String.join(" ", wordArr);
return res.toString();
}
/**
* 初始化字典树
*/
public TrieNode buildDict(List<String> dict) {
TrieNode root = new TrieNode();
for (String str : dict) {
TrieNode node = root;
for (int j = 0; j < str.length(); j++) {
node.children[str.charAt(j) - 'a'] = new TrieNode();
node = node.children[str.charAt(j) - 'a'];
}
node.isEnd = true;
}
return root;
}
/**
* 寻找替换的单词
*/
public String findReplaceWorld(TrieNode root, String word) {
TrieNode node = root;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < word.length(); i++) {
if (node.isEnd) {
break;
}
if (node.children[word.charAt(i) - 'a'] == null) {
return word;
}
sb.append(word.charAt(i));
node = node.children[word.charAt(i) - 'a'];
}
return sb.toString();
}
Tips：2025-05-30
Ⅱ：神奇的字典
题目描述
请实现有如下两个操作的神奇字典。
> 函数 buildDict，输入单词数组用来创建一个字典。
> 函数 search，输入一个单词，判断能否修改该单词中的一个字符，使修改之后的单词是字典中的一个单词。
题目分析
难度： ⭐⭐🐇🐇🐇
思路：
允许替换一个字符，但我们并不知道是哪个字符进行的替换。如果某一层找到的元素是空的，那么一定是这一层使用了替换的资格。后续的节点就应该按原来的字典搜索逻辑处理，而在这层前的也是按原来的搜索逻辑处理。由于后续遍历并不明确是哪一个下标的元素，所以此时应该是遍历所有位置。
我们定义一个遍历的字符下标，以及替换次数。对每一层都做同样的操作，找指定下标元素是否为空，如果是空，则进行遍历，并对替换次数加 1，如果替换次数超过了 1，那么肯定是不符合要求的。如果小于等于 1，并且字符下标增长至字符串的长度，且此时字典正好表示是一个单词，那么 此时说明符合要求。
参考代码
/**
* 建立单词字典
*
* @param dict 字符串数组
* @return 首节点
*/
public TrieNode buildDict(String[] dict) {
TrieNode root = new TrieNode();
for (String str : dict) {
TrieNode cur = root;
for (int i = 0; i < str.length(); i++) {
if (cur.children[str.charAt(i) - 'a'] == null) {
cur.children[str.charAt(i) - 'a'] = new TrieNode();
}
cur = cur.children[str.charAt(i) - 'a'];
}
cur.isEnd = true;
}
return root;
}
/**
* 搜索单词
*
* @param root 根节点
* @param word 单词
* @return 结果
*/
public boolean search(TrieNode root, String word) {
return dfs(root, word, 0, 0);
}
/**
* 遍历寻找
*
* @param root 根节点
* @param word 单词
* @param index 遍历下标
* @param count 替换计数
* @return 结果
*/
public boolean dfs(TrieNode root, String word, int index, int count) {
// 如果为 null，必然是 null
if (root == null) {
return false;
}
// 如果此时是单词，且长度和单词长度一致，且替换的元素计数小于 1，则说明但前位置满足条件
if (root.isEnd && index == word.length() && count <= 1) {
return true;
}
if (index < word.length()) {
// 是否找到了满足条件的单词
boolean flag = false;
for (int j = 0; j < 26; j++) {
int newCount = count;
// 如果为 null，则计数加 1，表示替换的数量
if (root.children[word.charAt(index) - 'a'] == null) {
newCount++;
}
// 下层依旧如此寻找，但指针加 1，即寻找的是下一个字符
flag = dfs(root, word, index + 1, newCount);
}
return flag;
}
return false;
}
Tips：2025-06-02
Ⅲ：最短的单词编码
题目描述
输入一个包含 n 个单词的数组，可以把它们编码成一个字符串和 n 个下标。例如，单词数组 ["time"，"me"，"bell"] 可以编码成一个字符串 "time＃bell＃"，然后这些单词就可以通过下标 [0， 2，5] 得到。对于每个下标，都可以从编码得到的字符串中相应的位置开始扫描，直到遇到'＃'字符前所经过的子字符串为单词数组中的一个单词。例如，从 "time＃bell＃" 下标为2的位置开始扫描，直到遇到'＃'前经过子字符串 "me" 是给定单词数组的第2个单词。给定一个单词数组，请问按照上述规则把这些单词编码之后得到的最短字符串的长度是多少？如果输入的是字符串数组 ["time"，"me"，"bell"]，那么编码之后最短的字符串是最短的单词编码 "time＃bell＃"，长度是 10。
题目分析
难度： ⭐⭐🐇🐇🐇
思路： 题目没有明显的前缀树特征，是一个基于单词后缀衍生的要求。而单词颠倒后后缀便可变形为前缀。所以如果把所有单词都逆序，那么就和前缀树比较相似了。根据逆序的单词组构建一颗前缀树，那么重构的单词编码应该由树顶到每个叶子节点所构成的单词的逆序组成，并且每个单词需要添加一个 # 用于分割。那么问题就转化成，前缀树根节点到每个叶子节点的深度加 1 后的总和（根节点深度记为 1）。
参考代码
// 这里使用了一个新加的构造方法，以选择是否初始化子节点
public TrieNode(boolean initChild) {
isEnd = false;
if (initChild) {
children = new TrieNode[26];
}
}
public int shortestWordCodeNum(String[] words) {
TrieNode root = new TrieNode(false);
for (String str : words) {
TrieNode cur = root;
str = new StringBuilder(str).reverse().toString();
for (int i = 0; i < str.length(); i++) {
if (cur.children == null) {
cur.children = new TrieNode[26];
cur.children[str.charAt(i) - 'a'] = new TrieNode(false);
} else if (cur.children[str.charAt(i) - 'a'] == null) {
cur.children[str.charAt(i) - 'a'] = new TrieNode(false);
}
cur = cur.children[str.charAt(i) - 'a'];
}
}
int[] res = new int[1];
traverse(root,0, res);
return res[0];
}
public void traverse(TrieNode node, int count, int[] res) {
if (node == null) {
return;
}
TrieNode[] children = node.children;
if (children == null) {
// 没有子节点，说明此节点为末尾节点，由于单词需要以#结尾，多一个字符，这里需加上 count + 1
res[0] += count + 1;
return;
}
for (TrieNode child : children) {
traverse(child, count + 1, res);
}
}
Tips：2025-06-04
Ⅳ：单词之和
题目描述
请设计实现一个类型 MapSum，它有如下两个操作。
> 函数 insert，输入一个字符串和一个整数，在数据集合中添加一个字符串及其对应的值。如果数据集合中已经包含该字符串，则将该字符串对应的值替换成新值。
> 函数 sum，输入一个字符串，返回数据集合中所有以该字符串为前缀的字符串对应的值之和。
题目分析
难度： ⭐🐇🐇🐇🐇
思路： 此题是针对前缀树的一个简单应用，计算值时，前缀遍历完后，针对后续字符进行全部遍历即可，遍历过程中，如果是单词则将值累计。
参考代码
import nep.akina.algorithm.base.TrieValNode;
/**
* @author nepakina
*/
public class MapSum {
private final TrieValNode root;
public MapSum() {
this.root = new TrieValNode();
}
public void insert(String word, int val) {
TrieValNode cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.children[c - 'a'] == null) {
cur.children[c - 'a'] = new TrieValNode();
}
cur = cur.children[c - 'a'];
}
cur.isEnd = true;
cur.val = val;
}
public int sum(String prefix) {
TrieValNode cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.children[c - 'a'] == null) {
return 0;
}
cur = cur.children[c - 'a'];
}
return sumChildVal(cur);
}
public int sumChildVal(TrieValNode node) {
if (node == null) {
return 0;
}
int res = 0;
// 此处判断是否是单词其实没有必要，因为只有是单词 val 才会有值
// 当不判断 isEnd 时，新增单词时也不必维护 isEnd 的值
if (node.isEnd) {
res += node.val;
}
for (int i = 0; i < node.children.length; i++) {
res += sumChildVal(node.children[i]);
}
return res;
}
}
Tips：2025-06-18
Ⅴ：最大的异或
输入一个整数数组（每个数字都大于或等于0），请计算其中任意两个数字的异或的最大值。例如，在数组 [1，3，4，7] 中，3 和 4 的异或结果最大，异或结果为 7。
题目分析
难度： ⭐⭐🐇🐇🐇
思路：
首先能够想到暴力的计算方式求解，将每个元素和其他元素一一求异或，最后取最大值，暴力方式的复杂度将是 O(n²)。
异或计算规则是同位相同取 0，不相同取 1；此时求最大异或，即尽可能的使得元素的位异或结果为 1，且应该是优先左侧位计算。
这个过程可以转化为，指定一个整数，随后从整数的最高位开始遍历每一位，寻找其他整数中与已知整数相同位的值相反的整数集合；筛选集合后，继续寻找下一位，重复这个操作，知道整数位全部遍历结束。在这个过程中，记录寻找过程中每一位异或的结果，这个结果就是当前指定整数的最大异或值。随后对其他整数也进行上诉操作，最终取最大值。
这个寻找过程不难看出，其非常类似一个前缀树，我们可以整数最大位数 (32) 为深度，2 为宽度 (每一位都只有 0 和 1 两个值)，构建一颗前缀树，寻找时按最长 32 位开始从左到右依次在树种寻找相反的位（不存在相反的位则取同值位即可），计算异或值（集体左移为新的异或结果位留位置，如果相反的位有值，则左移后加 1，否则仅左移）。对每个整数位遍历后，记录最大异或值；最终结果即为所求。
改过程遍历次数为 n * 32，32 是常数，所以时间复杂度为 O(n)。
参考代码
public int findMaxXor(int[] nums) {
TrieNode root = buildTrieNode(nums);
int res = 0;
for (int num : nums) {
TrieNode cur = root;
int xor = 0;
for (int j = 31; j >= 0; j--) {
int bit = (num >> j) & 1;
// 如果对立的元素存在，那么此时取对立元素，比计算此时的异或值
if (cur.children[1 - bit] == null) {
// 此时原值应该集体左移，给新元素空位，通过+1对新元素位进行填充
xor = (xor << 1) + 1;
cur = cur.children[1 - bit];
} else {
// 不存在对立是，仅左移
xor = xor << 1;
cur = cur.children[bit];
}
}
res = Math.max(res, xor);
}
return res;
}
public TrieNode buildTrieNode(int[] nums) {
// 这里实际只用到了子节点中下标为 0 和 1 的元素
TrieNode root = new TrieNode();
for (int num : nums) {
TrieNode cur = root;
for (int j = 31; j >= 0; j--) {
// 获取当前位
int bit = (num >> j) & 1;
if (cur.children[bit] == null) {
cur.children[bit] = new TrieNode();
}
cur = cur.children[bit];
}
}
return root;
}
Tips：2025-06-18
三、章节小结
前缀树通常用来保存字符串，它的节点和字符串的字符对应，而路径和字符串对应。如果只考虑英文小写字母，那么前缀树的每个节点有26个子节点。为了标注某些节点和字符串的最后一个字符对应，前缀树节点中通常需要一个布尔类型的字段。
前缀树经常用来解决与字符串查找相关的问题。和哈希表相比，在前缀树中查找更灵活。既可以从哈希表中找出所有以某个前缀开头的所有单词，也可以找出修改了一个（或多个）字符的字符串。
使用前缀树解决问题通常需要两步：第1步是创建前缀树，第2步是在前缀树中查找。