注意：学习本篇最少应知道什么是树结构和哈希表怎么用。
前缀树又叫字典树，英文名trie。每个样本 都从头节点开始 根据 前缀字符或者前缀数字 建出来的一棵大树，就是前缀树。没有路就新建节点；已经有路了，就复用节点。
前缀树的使用场景：需要根据前缀信息来查询的场景
前缀树的优点：根据前缀信息选择树上的分支，可以节省大量的时间
前缀树的缺点：比较浪费空间，和总字符数量有关，字符的种类有关
一、前缀树的原理和代码
前缀树是通过多个节点之间的路来存储信息，并进行快速查询的。比如我们有一个字符串"abc"，从1节点开始（0节点弃用，具体原因后面说明），注意，在前缀树中，节点不存储字符串信息，节点一般有pass和end两个属性，分别表示经过这个节点的次数和以这个节点做结尾的次数。用节点之间的路来存储字符串信息，比如1节点到2节点之间的路代表'a'，2节点到3节点之间的路代表'b'，3节点到4节点之间的路代表'c'。之后再存储字符串就会有节点复用、路复用，比如再来一个字符串"abd"，从1节点开始直到3节点都一样，然后3节点没有代表'd'的路，所以新建节点、新建路，3节点到5节点之间的路代表'd'。在加入两个字符串后，1~5节点pass分别为[2, 2, 2, 1, 1]，end分别为[0, 0, 0, 1, 1]。这样，一个前缀树的结构就建好了，之后对于前缀信息的查询将会非常快速。
对于实现前缀树，一般有两种方式。
类描述的实现方式。不推荐，虽然最常用。
- 路的可能性范围较小，用固定数组实现路
- 路的可能性范围较大，用哈希表实现路
静态数组的实现方式。推荐，不仅笔试，就连比赛也能保证使用。
- 一切都是静态数组来实现，提交准备好够用的空间
- 如果路的可能性范围较大，就用每一位的信息建树
下面就介绍静态数组的实现方式。
其中的方法如下所示。
// 将字符串word插入前缀树中
void insert(string word);
// 返回前缀树中字符串word的实例个数
int search(string word);
// 返回前缀树中以prefix为前缀的字符串个数
int prefixNumber(string prefix);
// 从前缀树中移除字符串word
void delete(string word);测试链接：https://www.nowcoder.com/practice/7f8a8553ddbf4eaab749ec988726702b
我们用一个m×n的二维数组trie存储节点和节点之间路的代表，m表示最大节点个数，一定保证节点不会不够用，n表示路的所有可能性，比如对于小写英文字符串n就是26，而trie[i][j]表示i节点通过代表j的路到trie[i][j]节点上了。然后，每个节点的pass和end属性用两个m长度的一维数组表示，arr[i]表示i节点的pass或end值为arr[i]。
代码如下。
#include <iostream>
#include <string>
using namespace std;
#define MAX_VALUE 200000
int trie[MAX_VALUE][26] = {0};
int Pass[MAX_VALUE] = {0};
int End[MAX_VALUE] = {0};
int m;
int cnt = 1;
void insert(string word) {int cur = 1;Pass[cur]++;for (int i = 0; i < word.size(); ++i) {if (trie[cur][word[i] - 'a'] == 0) {trie[cur][word[i] - 'a'] = ++cnt;cur = trie[cur][word[i] - 'a'];Pass[cur]++;} else {cur = trie[cur][word[i] - 'a'];Pass[cur]++;}}End[cur]++;
}
void Delete(string word) {int cur = 1;Pass[cur]--;for (int i = 0; i < word.size(); ++i) {cur = trie[cur][word[i] - 'a'];Pass[cur]--;}End[cur]--;
}
bool search(string word) {int cur = 1;for (int i = 0; i < word.size(); ++i) {if (trie[cur][word[i] - 'a'] == 0) {return false;}cur = trie[cur][word[i] - 'a'];}return End[cur] != 0;
}
int prefixNumber(string pre) {int cur = 1;for (int i = 0; i < pre.size(); ++i) {if (trie[cur][pre[i] - 'a'] == 0) {return 0;}cur = trie[cur][pre[i] - 'a'];}return Pass[cur];
}
int main() {int op;string s;cin >> m;for (int turn = 0; turn < m; ++turn) {cin >> op;getchar();cin >> s;switch (op) {case 1:insert(s);break;case 2:Delete(s);break;case 3:cout << (search(s) ? "YES" : "NO") << endl;break;case 4:cout << prefixNumber(s) << endl;break;}}
}其中，将trie数组中的0试做未给节点分配路，所以0节点弃而不用，以防产生歧义。
下面将通过几个题目进一步加深理解前缀树和其应用。
二、前缀树的相关题目
题目一
测试链接：https://www.nowcoder.com/practice/c552d3b4dfda49ccb883a6371d9a6932
分析：这个就是将a数组前后相减处理后放入前缀树，然后对b数组做同样处理后，查询以b数组为前缀的个数。注意，因为以一个差值作为路代表，路的种类过多，所以将整数差开处理，即比如"32"，处理为"3""2"，然后每个数结束后增加"#"作为数之间的分隔符。这样路的种类只需12种，0~9，'#'，'-'。代码如下。
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param b int整型vector<vector<>>* @param a int整型vector<vector<>>* @return int整型vector*/int trie[2000000][12] = {0};int Pass[2000000] = {0};int End[2000000] = {0};int cnt = 1;void insert(string word) {int cur = 1;Pass[cur]++;for (int i = 0; i < word.size(); ++i) {int path = (word[i] == '#' ||word[i] == '-') ? (word[i] == '#' ? 11 : 10) : (word[i] - '0');if (trie[cur][path] == 0) {trie[cur][path] = ++cnt;cur = trie[cur][path];Pass[cur]++;} else {cur = trie[cur][path];Pass[cur]++;}}End[cur]++;}int prefixNumber(string pre) {int cur = 1;for (int i = 0; i < pre.size(); ++i) {int path = (pre[i] == '#' ||pre[i] == '-') ? (pre[i] == '#' ? 11 : 10) : (pre[i] - '0');if (trie[cur][path] == 0) {return 0;}cur = trie[cur][path];}return Pass[cur];}string transfer(int num) {string s = "";int arr[10];int left = 0;int right = 0;while (num != 0) {arr[right++] = num % 10;num /= 10;}while (left < right) {s += (arr[--right] + '0');}s += '#';return s;}vector<int> countConsistentKeys(vector<vector<int>>& b,vector<vector<int>>& a) {vector<int> ans;for (int i = 0; i < a.size(); ++i) {string s = "";for (int j = 1; j < a[i].size(); ++j) {int num = a[i][j] - a[i][j - 1];s += transfer(num);}insert(s);}for (int i = 0; i < b.size(); ++i) {string s = "";for (int j = 1; j < b[i].size(); ++j) {int num = b[i][j] - b[i][j - 1];s += transfer(num);}ans.push_back(prefixNumber(s));}return ans;}
};其中，前缀树的方法只需两个，故将不需要的删除。
题目二
测试链接：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
分析：由于int型的32位在最左侧的1的左边可能存在多位的0，会增加处理时间，所以只需参考数组中最大值所需要的位数，从而在对数组中每个数进行前缀数插入时，只需要处理相应位数即可。对于数组中的每一位数去寻找到对于这个数能够得到的理想最大异或值。对于这个数，每一位进行判断，如果是1则理想的数，这一位是0；如果是0，理想数的这一位就是1，通过前缀树查询理想数的1或0是否能够得到，如果不能，理想数的这一位就是理想位数的异或值，1变为0，0变为1。得到理想数的这一位数后，对理想数的这一位数和正在处理的数的这一位数的异或结果进行左移相应位数，然后和当前异或结果或求值。处理完所有位数后，即可得到对于这一个数所能得到的最大异或值。然后得到数组中每一位数所能得到的最大异或值，即可求得总体最大异或值。代码如下。
class Solution {
public:int trie[3000000][2] = {0};int Pass[3000000] = {0};int End[3000000] = {0};int cnt = 1;void insert(int num, int high) {int cur = 1;Pass[cur]++;for (int i = high; i >= 0; --i) {int path = (((num >> i) & 1) == 0) ? 0 : 1;if (trie[cur][path] == 0) {trie[cur][path] = ++cnt;cur = trie[cur][path];Pass[cur]++;} else {cur = trie[cur][path];Pass[cur]++;}}End[cur]++;}int prefixNumber(int num, int high, int low) {int cur = 1;for (int i = high; i >= low; --i) {int path = (((num >> i) & 1) == 0) ? 0 : 1;if (trie[cur][path] == 0) {return 0;}cur = trie[cur][path];}return Pass[cur];}int findMaximumXOR(vector<int>& nums) {int ans = 0;int m = *(max_element(nums.begin(), nums.end()));int bit = 31;while ((bit >= 0) && (!((m >> bit) & 1))) {--bit;}for (int i = 0; i < nums.size(); ++i) {insert(nums[i], bit);}for (int i = 0; i < nums.size(); ++i) {int desire = 0;int cur = 1;for (int j = bit, status, want; j >= 0; --j) {status = (((nums[i] >> j) & 1) == 0 ? 0 : 1);want = status ^ 1;if (!trie[cur][want]) {want ^= 1;}desire |= ((want ^ status) << j);cur = trie[cur][want];}ans = ((ans > desire) ? ans : desire);}return ans;}
};其中，m是数组中的最大值，bit是需要处理的位数，desire是对于正在处理的数的当前最大异或值，status是正在处理的数某一位的值，want是对于正在处理的数的理想数某一位的值。
当然，这个题如果使用哈希表会更快，不过本文主要是侧重前缀树的解法。下面给出哈希表解法（java）。
import java.util.HashSet;public class Solution {public int findMaximumXOR(int[] nums) {int max = Integer.MIN_VALUE;for (int num : nums) {max = Math.max(num, max);}int ans = 0;HashSet<Integer> set = new HashSet<>();for (int i = 31 - Integer.numberOfLeadingZeros(max); i >= 0; i--) {// ans : 31....i+1 已经达成的目标int better = ans | (1 << i);set.clear();for (int num : nums) {// num : 31.....i 这些状态保留，剩下全成0num = (num >> i) << i;set.add(num);// num ^ 某状态 是否能 达成better目标，就在set中找 某状态 : better ^ numif (set.contains(better ^ num)) {ans = better;break;}}}return ans;}}题目三
测试链接：https://leetcode.cn/problems/word-search-ii/
分析：可以看出，这道题的主体思路是一个回溯算法，那么回溯算法就是在考剪枝能力。我们可以通过前缀树进行三个地方的优化，从而使速度更快。在将所有单词插入前缀树之后，对于board二维数组进行遍历的时候，前缀树可以指导每次进递归对哪个方向进行遍历，这是第一个地方的剪枝。在将一个单词查询到之后，从前缀树上删除这个这个单词的痕迹，从而使后续不再对这个单词进行遍历，这是第二个地方的剪枝。可以在前缀数上把end信息改为字符串信息存储，一个单词结尾节点的end是这个单词的字符串，这个单词的中间节点的end设为空值或者空字符串。这样在遍历到这个单词的结尾节点的时候可以直接获取到这个单词，这是第三个地方的优化。这样由前缀树指导的剪枝回溯，可以使速度大大提升。代码如下。
class Solution
{
public:int trie[100000][26] = {0};int Pass[100000] = {0};string End[100000] = {""};int cnt = 1;int f(int row, int column, vector<string> &ans, int cur, vector<vector<char>> &board){if(row < 0 || row == board.size() || column < 0 || column == board[0].size() || (board[row][column] == 0)){return 0;}char temp = board[row][column];int road = temp - 'a';cur = trie[cur][road];if(Pass[cur] == 0){return 0;}int fix = 0;if(End[cur] != ""){fix++;ans.push_back(End[cur]);End[cur] = "";}board[row][column] = 0;fix += f(row-1, column, ans, cur, board);fix += f(row+1, column, ans, cur, board);fix += f(row, column-1, ans, cur, board);fix += f(row, column+1, ans, cur, board);Pass[cur] -= fix;board[row][column] = temp;return fix;}void build(vector<string> &words){cnt = 1;for(int i = 0;i < words.size();++i){int cur = 1;Pass[cur]++;for(int j = 0, path;j < words[i].size();++j){path = words[i][j] - 'a';if(trie[cur][path] == 0){trie[cur][path] = ++cnt;}cur = trie[cur][path];Pass[cur]++;}End[cur] = words[i];}}vector<string> findWords(vector<vector<char>> &board, vector<string> &words){build(words);vector<string> ans;for(int i = 0;i < board.size();++i){for(int j = 0;j < board[0].size();++j){f(i, j, ans, 1, board);}}return ans;}
};其中build方法整合和插入方法，f方法是主体回溯函数，同时对于同一条路径，采用遍历过对其ASCII码值赋0实现判断是否被访问。fix是当前节点及后续节点查询到多少单词，然后在前缀树上消除这些单词的痕迹。
)
