Trie树可以支持快速存储和查找某个字符串在字典中是否出现过以及出现的次数
模板：
#include <iostream>
using namespace std;
const int N = 100010;
char str[N];
int n ;
int son[N][26],cnt[N],idx;
void insert(char str[]){//节点索引为0表示为空 也可以表示为根节点，一开始就从根节点开始，根节点是不存任何东西的
int p = 0 ;//从根节点开始走,用来遍历，往下一直走。从第一个字母之前开始走（也就是根节点），进入循环才是处理第一层，也就是插入第一个字母 一定要注意
for(int i = 0;str[i];i ++) {
int u = str[i] - ‘a‘;//当前应该是走往那个分支的方向走，就是26个字母中的哪一个
if(!son[p][u]) son[p][u] = ++ idx; //下一个字母是什么 然后看存不存在 如果存在 就直接往下一个走 ，如果不存在就创建一个
p = son[p][u]; //走不通就创建一个，然后再走，走得通就直接走 ，这里不能直接加else
...//对当前这一层 也就是这个字母做处理
} a
cnt[p] ++; //然后这个节点结尾的字符串个数+ 1
}
int query(char str[]){
int p = 0 ;//从第一个字母之前开始走，进入循环才是处理第一层，也就是插入第一个字母 一定要注意
for(int i = 0;str[i];i ++) {
int u = str[i] - ‘a‘;//
if(!son[p][u]) return 0;//如果下一个字母不存在 就直接返回0
p = son[p][u];//如果存在就直接往下走
...//对当前这一层 也就是这个字母做处理
}
return cnt[p];
}
什么时候用：
1.有一个列表，一堆重点词，然后一个或者几个长字符串。要快速存储和搜索，这个时候就可以用trie。提到词典就可以想到trie树
2.给一堆敏感词然后给你一个长字符串，然后找到敏感词再字符串中的位置、
3.如果见到与前缀树有关 也可以想到就是trie
注意点和易错点：
1.是str[i] - ‘a‘不是str[i] - ‘0‘
2.看清楚是只有小写字母还是还有大写字母
3,就是一个非满26叉数，插入和查找过程就是在遍历这棵树，就是在一直往下走
4.在trie + dfs遍历trie的过程中for中的是son[p][i]而不是son[p][u]
略：就是上面的代码。
class MagicDictionary {
/** Initialize your data structure here. */
int[][] son = new int[10010][26];
int idx;
boolean flag = false;
int[] cnt = new int[100010];
public MagicDictionary() {
}
public void buildDict(String[] d) {
for(int i = 0;i < d.length;i ++) {
insert(d[i]);
}
}
void insert(String s) {
int p= 0 ;
for(int i = 0;i < s.length();i ++) {
int u = s.charAt(i) - ‘a‘;
if(son[p][u] == 0) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++;
}
public boolean search(String str) {
flag = false;
dfs(str,0,0,1);
return flag;
}
void dfs(String str,int p,int u,int t) {
//各种合适和不合适的终止条件
if(flag) return ;//递归限制条件
if(u == str.length()) {//如果遍历完了所有的数，而且t用了 而且是有字符串，就有,然后返回，否则不行
if(t != 1 && cnt[p] != 0){
flag = true;
return;
}
else return ;
}
int now = str.charAt(u) - ‘a‘;
//做选择，进入各种方案的递归决策子树
if(t == 1)//方案1： 如果t = 1那么可以随便走一跳trie数的分支
for(int i = 0;i < 26;i ++) {
if(flag) return ;
if(son[p][i] != 0) {
if(i == now) dfs(str,son[p][i],u + 1,t);
else dfs(str,son[p][i],u + 1,t - 1);
}
}
else {//如果t被用了 ，那就只能老老时时望下走
if(son[p][now] == 0) return ;//剪枝
else dfs(str,son[p][now],u + 1,0);
}
return ;
}
}
/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary obj = new MagicDictionary();
* obj.buildDict(dictionary);
* boolean param_2 = obj.search(searchWord);
*/
dfs一定要深刻理解做选择和层的含义 不一定要for循环 各种奇奇怪怪的各种条件才能做得选择也有很多，dfs就是找到选择和层两个关键，dfs还有注意u是== n 还是n - 1
给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。
若无答案，则返回空字符串。
示例 1：
输入：
words = ["w","wo","wor","worl", "world"]
输出："world"
解释：
单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。
示例 2：
输入：
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出："apple"
解释：
"apply"和"apple"都能由词典中的单词组成。但是"apple"的字典序小于"apply"。
提示：
所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。
class Solution {
int[][] son = new int[10010][26];
int idx;
int[] cnt = new int[10001];
int len = 0 ;
String res ="";
public String longestWord(String[] words) {
if(words.length == 0) return "";
int n = words.length;
for(int i = 0;i < n;i ++) {
insert(words[i]);
}
dfs(0,0,"");
return res;
}
void insert(String str) {
int p = 0;
for(int i = 0;i < str.length();i ++) {
int u = str.charAt(i) - ‘a‘;
if(son[p][u] == 0) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++;
}
void dfs(int p,int u,String t){//形参递归变量十分常见了
if(u > len) {//String的打擂法
res = t;
len = u;
}
//明显不会无线深搜下去，所以不一定要有终止条件
//做出选择
for(int i = 0;i < 26;i ++) {
if(son[p][i] != 0 && cnt[son[p][i]] != 0) {
char a =(char)(i + ‘a‘);//char的强制转化
dfs(son[p][i],u + 1,t + a);//形参写在dfs中 相当于回溯
}
}
return ;
}
}
又是一道trie树构建+ dfs的问题，
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：
WordDictionary() 初始化词典对象
void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 ‘.‘ ，每个 . 都可以表示任何一个字母。
示例：
输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]
解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
提示：
1 <= word.length <= 500
addWord 中的 word 由小写英文字母组成
search 中的 word 由 ‘.‘ 或小写英文字母组成
最调用多 50000 次 addWord 和 search
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-add-and-search-words-data-structure
class WordDictionary {
int[][] son = new int[100010][26];
int[] cnt = new int[100010];
int idx;
boolean flag = false;
/** Initialize your data structure here. */
public WordDictionary() {
}
/** Adds a word into the data structure. */
public void addWord(String word) {
int p = 0 ;
for(int i = 0;i < word.length();i ++) {
int u = word.charAt(i) - ‘a‘;
if(son[p][u] == 0) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++;
}
/** Returnas if the word is in the data structure. A word could contain the dot character ‘.‘ to represent any one letter. */
public boolean search(String word) {
flag = false;
dfs(0,0,word);
return flag;
}
void dfs(int u ,int p,String str){
if(flag) return ;//如果已经找到了答案 提前终止深搜
if(u == str.length()) {//递归出口1
if(cnt[p] != 0) {
flag = true;
return ;
}else return ;
}
//做选择 进入对应的深搜递归决策子树
if(str.charAt(u) == ‘.‘) {//第一种情况可以做的选择
for(int i = 0;i < 26;i ++) {
if(flag) return;//剪枝，如果已经找到了答案 就提前终止搜索，再每个选择前面加上这一句话
if(son[p][i] != 0) dfs(u + 1,son[p][i],str);
}
}else {//第二种情况可以做的选择
if(flag) return;//剪枝
int t = str.charAt(u) - ‘a‘;
if(son[p][t] == 0) return;
else
dfs(u + 1,son[p][t],str);
return ;
}
}
}
就是trie的构建和一个查询 但是有点变换就是多一个.通配符需要进行考虑 ，就可能有多种需选择，每种选择都是不同的方案 然后走的是不同的分支，所以要使用dfs进行操作。因为一个选择的也就是只有一个分支的dfs深度优先搜索就相当于循环的作用，如果多个选择，就相当于有枚举多个方案的作用。
原文：https://www.cnblogs.com/yizhanwillsucceed/p/13809692.html