一、算法理解

参考：字典树(前缀树)_越看越喜欢啊-CSDN博客_字典树

字典树，叫前缀树可能更好理解。

Trie又被称为前缀树、字典树，所以当然是一棵树。

上面这棵Trie树包含的字符串集合是{in, inn, int, tea, ten, to}。每个节点的编号是我们为了描述方便加上去的。树中的每一条边上都标识有一个字符。这些字符可以是任意一个字符集中的字符。比如对于都是小写字母的字符串，字符集就是’a’-‘z’；对于都是数字的字符串，字符集就是’0’-‘9’；对于二进制字符串，字符集就是0和1。

比如上图中3号节点对应的路径0123上的字符串是inn，8号节点对应的路径0568上的字符串是ten。终结点与集合中的字符串是一一对应的。

【原理】：

下面我们来讲一下对于给定的字符串集合{W1, W2, W3, … WN}，如何创建对应的Trie树。

其实上Trie树的创建是从只有根节点开始，通过依次将W1, W2, W3, … WN插入Trie中实现的。所以关键就是之前提到的Trie的插入操作。

具体来说，Trie一般支持两个操作：

1. Trie.insert(W)：第一个操作是插入操作，就是将一个 字符串W 加入到集合中。


2. Trie.search(S)：第二个操作是查询操作，就是查询一个 字符串S 是不是在集合中。

1、插入操作

（1）假设我们要插入字符串”in”。

我们一开始位于根，也就是0号节点，我们用P=0表示。我们先看P是不是有一条标识着i的连向子节点的边。没有这条边，于是我们就新建一个节点，也就是1号节点，然后把1号节点设置为P也就是0号节点的子节点，并且将边标识为i。最后我们移动到1号节点，也就是令P=1。



这样我们就把”in”的i字符插入到Trie中了。

然后我们再插入字符n，也是先找P也就是1号节点有没有标记为n的边。还是没有，于是再新建一个节点2，设置为P也就是1号节点的子节点，并且把边标识为n。最后再移动到P=2。这样我们就把n也插入了。由于n是”in”的最后一个字符，所以我们还需要将P=2这个节点标记为终结点。

（2）现在我们再插入字符串”inn”

过程也是一样的，从P=0开始找标识为i的边，这次找到1号节点。于是我们就不用创建新节点了，直接移动到1号节点，也就是令P=1。再插入字符n，也是有2号节点存在，所以移动到2号节点，P=2。最后再插入字符n这时P没有标识为n的边了，所以新建3号节点作为2号节点的子节点，边标识为n，同时将3号节点标记为终结点：

（3）将后面的字符串int tea ten to都插入之后，就得到了我们一开始给出的Trie：

【总结】：

插入操作伪码如下：

2、查询操作

下面我们再讲一下如何查询Trie树中是不是包含字符串S，也就是之前提到的查找操作。

查找其实比较简单。我们只要从根节点开始，沿着标识着S[1] -> S[2] -> S[3] … -> S[S.len]的边移动，如果最后成功到达一个终结点，就说明S在Trie树中；如果最后无路可走，或者到达一个不是终结点的节点，就说明S不在Trie树中。

如果是查找”te”，就会从0开始经过5最后到达6。但是6不是终结点，所以te没在Trie树中。如果查找的是”too”，就会从0开始经过5和9，然后发现之后无路可走：9号节点没有标记为o的边连出去。所以too也不在Trie中。

查找操作伪码：

3、Trie树的代码实现参考

数组方式实现

要写代码实现一个Trie首先就要确定如何存储一个Trie结构。这里用一个二维数组来存储：

int trie[MAX_NODE]/[CHARSET];

int k;

• 其中MAX_NODE是trie中最大能存储的节点数目


• CHARSET是字符集的大小


• k是当前trie中包含有多少个节点。


• Trie[i]/[j]的值是0表示trie树中i号节点，并有一条连出去的边，边上的字符是字符集中第j个字符（从0开始）；


• trie[i]/[j]的值是正整数x，表示trie树中i号节点，有一条连出去的边，边上的字符是字符集中第j个字符，并且这条边的终点是x号节点。

PS：Tire树需要保存的值：

1）边的起节点

2）边的终节点

3）边的字符。

如上采用数组方式，非0的[i]/[j]，其值表示边连接的下一个节点，i表示当前节点，j表示边的字符。

#include
#include
#include
using namespace std;
const int MAX_NODE = 1000000 + 10;
const int CHARSET = 26;
int trie[MAX_NODE][CHARSET] = {0};
int color[MAX_NODE] = {0}; //记录是不是树的叶子节点
int k = 1;
void insert(char *w){
int len = strlen(w);
int p = 0;
for(int i=0; i int c = w[i] - 'a';
if(!trie[p][c]){
trie[p][c] = k;
k++;
}
p = trie[p][c];
}
color[p] = 1;
}
int search(char *s){
int len = strlen(s);
int p = 0;
for(int i=0; i int c = s[i] - 'a';
if(!trie[p][c]) return 0;
p = trie[p][c];
}
return color[p] == 1;
}
int main(){
int t,q;
char s[20];
scanf("%d%d", &t,&q);
while(t--){
scanf("%s", s);
insert(s);
}
while(q--){
scanf("%s", s);
if(search(s)) printf("YES\n");
else printf("NO\n");
}
return 0;
}


二、适用场景

三、注意事项

【个人理解】

1. 当然Java中也可以采用这种方式（个人理解）。节点通过Node { Map; xxxx}表示：key表示字符，value表示重点Node索引, xxx表示节点需要记录的其它属性（如：节点所在树深度）。如果所有节点需要遍历，可以考虑同时使用ArrayList记录节点全集。


2. 如果需要计算叶子节点相关，则最好每个Node中保存一个Count，记录当前Node的边数。（参考单词压缩编码的例子）。Node节点，包含Count和Node[]，[]索引表示边、值表示下个Node。

【字典树关键操作】

1）Insert(String)，单词插入树

2）search(String)，判断单词是否存在指定单词。（需到叶子节点）

3）searchWith(String)，判断字典树中是否有单词是指定前缀

四、使用案例

1）单词压缩编码（leetCode）

给定义一组单词words，按照如下规则进行编码，编码后结果由：助记字符串 s 和 下标数组 indices 组成。输出最小 助记字符串 长度。

如:

1）单词组是words = ["time", "me", "bell"]

2）编码后结果为s = "time#bell#" 和 indices = [0, 2, 5]

如上：单词组words和编码结果的关系如下：

words[0] = "time" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"

words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"

words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"

【思路一】存储后缀

如果单词 X 是 Y 的后缀，那么单词 X 就不需要考虑了，因为编码 Y 的时候就同时将 X 编码了。例如，如果 words 中同时有 "me" 和 "time"，我们就可以在不改变答案的情况下不考虑 "me"。

如果单词 Y 不在任何别的单词 X 的后缀中出现，那么 Y 一定是编码字符串的一部分。

因此，目标就是保留所有不是其他单词后缀的单词，最后的结果就是这些单词长度加一的总和，因为每个单词编码后后面还需要跟一个 # 符号。

代码参考：

class Solution {
/*
*
* 方式一：逐个单词遍历其后缀节点，删除为其后缀的单词
*/
public int compressWords(String[] words) {
if (words == null || words.length == 0)
{
return 0;
}
ArrayList wordsList = new ArrayList<>(Arrays.asList(words));
wordsList.sort((i, j) -> j.length() - i.length());
for (String word: words) {
for (int i=1; i wordsList.remove(word.substring(i));
}
}
int sum = 0;
for (String word2: wordsList) {
sum += (word2.length() + 1);
}
return sum;
}
}


【思路二】字典树

如方法一所说，目标就是保留所有不是其他单词后缀的单词。

去找到是否不同的单词具有相同的后缀，我们可以将其反序之后插入字典树中。例如，我们有 "time" 和 "me"，可以将 "emit" 和 "em" 插入字典树中。

然后，字典树的叶子节点（没有孩子的节点）就代表没有后缀的单词，统计叶子节点代表的单词长度加一的和即为我们要的答案。

代码参考：

字典树结构：
class Solution {
public int minimumLengthEncoding(String[] words) {
TrieNode trie = new TrieNode();//根节点

Map nodes = new HashMap();
for (int i = 0; i String word = words[i];
TrieNode cur = trie;
for (int j = word.length() - 1; j >= 0; --j) {
cur = cur.get(word.charAt(j));
}
nodes.put(cur, i); //记录单词索引---单词终结节点
}
int ans = 0;
for (TrieNode node: nodes.keySet()) {
if (node.count == 0) { //终结节点 的单词长度之和
ans += words[nodes.get(node)].length() + 1;
}
}
return ans;
}
}
//节点的边对应的下个节点，数组下标和'a'的差值表示边
class TrieNode {
TrieNode[] children;
int count;
TrieNode() {
children = new TrieNode[26];
count = 0;
}
public TrieNode get(char c) {
if (children[c - 'a'] == null) {
children[c - 'a'] = new TrieNode();
count++;
}
return children[c - 'a'];
}
}


字典树结构2：
class Solution {
// 定义节点结构，通过字符关联下一个节点。
class Node {
HashMap relatiOnMap= new HashMap();
Integer deep;
}
/*
* 方式二，采用字典树方式
*
*/
public int compressWords2(String[] words) {
if (words.length == 0) {
return 0;
}
// 创建根节点
ArrayList nodeList = new ArrayList();
nodeList.add(new Node());
//排序，字典树中先插入最长的单词
ArrayList wordsList = new ArrayList<>(Arrays.asList(words));
wordsList.sort((i, j) -> j.length() - i.length());
for(String word: words) {
if(!search(nodeList, word)) {
insert(nodeList, word);
}
}
int sum = 0;
for (Node node: nodeList) {
if (node.relationMap.size() == 0) {
//单词长度 + '#'
sum += node.deep + 1;
}
}
return sum;
}
private void insert(ArrayList nodeList, String word) {
if (word == null || word.length() == 0 || nodeList.size() == 0) {
return;
}
Node curNode = nodeList.get(0);
for (int i= word.length()-1; i>=0; i--) {
Character charac = word.charAt(i);
HashMap nextMap = curNode.relationMap;
if(nextMap.get(charac) == null) {
Node tmpNode = new Node();
tmpNode.deep = word.length() - i;
nextMap.put(charac, tmpNode);
nodeList.add(tmpNode);
curNode = tmpNode;
}
else {
curNode = nextMap.get(charac);
}
}
return;
}
private boolean search(ArrayList nodeList, String word) {
if (word == null || word.length() == 0 || nodeList.size() == 0) {
return false;
}
Node curNode = nodeList.get(0);
for (int i = word.length() - 1; i >= 0; i--) {
HashMap nextMap = curNode.relationMap;
if (nextMap.get(word.charAt(i)) == null) {
return false;
} else {
curNode = nextMap.get(word.charAt(i));
}
}
return true;
}
}