前缀树是N叉树的一种形式，常用于存储字符串，树中每一个节点表示一个字符。
前缀树重要的存在价值是搜索速度，典型的利用空间换时间，时间复杂度为O(n)，n是树的深度。
Trie
上图中存储了四个单词：am、bad、be、so，位于叶子节点，叶子节点一定为词，但词不一定位于叶子节点。除了存储词的节点外，其余节点称为前缀。如ba，在树中并不是一个词，但他是bad词的前缀，前缀的重要作用就是减少存储空间，具有相同前缀的不同单词，只需存储差异部分，大大减少了空间的存储。
我所喜欢的数据结构：
public class TrieNode {
public boolean isWord;
public HashMap<Character, TrieNode> nexts = new HashMap<Character, TrieNode>();
}
Trie常见的操作：
插入
private void insert(String word, TrieNode root) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
if (node.nexts.get(word.charAt(i)) == null) {//没有前缀
node.nexts.put(word.charAt(i), new TrieNode());
}
node = node.nexts.get(word.charAt(i));//切记切换到子节点，否则全部存在了一层
}
node.isWord = true;//标记单词存储结束，其余节点为前缀
}
查找单词
private boolean search(String word, TrieNode root) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
if (node.nexts.get(word.charAt(i)) == null) {
return false;//中途查找失败，就失败
}
node = node.nexts.get(word.charAt(i));//切换到下一层
}
return node.isWord;//查找到了但不一定是单词，有可能是其他单词的前缀，因此需要判断
}
查找前缀
public boolean startsWith(String prefix) {
char[] chars=prefix.toCharArray();
TrieNode node=root;
for(int i=0;i<chars.length;i++){
if(node.nexts.get(chars[i])==null){
return false;//没查完就到顶了，失败
}else{
node=node.nexts.get(chars[i]);//查找下一层
}
}
return true;//查找到了一定是前缀，与查找单词不同
}
Map Sum Pairs
https://leetcode.com/explore/learn/card/trie/148/practical-application-i/1058/
这个题目实在是翻译不出来啊！题意：插入多个单词（apple、app）给每一个词赋值apple=3、app=2，当输入前缀ap时，返回以ap为前缀的所有单词值的和。
Example：
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
public int sum(String prefix) {
char[] chars=prefix.toCharArray();
TrieNode node=root;
for(int i=0;i<chars.length;i++){
if(node.nexts.get(chars[i])==null){//前缀找到一半就夭折了
return 0;
}else{
node=node.nexts.get(chars[i]);//去下一层寻找
}
}
return value(node);//找到了前缀的最后一个节点
}
private int value(TrieNode root){
TrieNode node=root;
int sum=0;
if(node==null){
return 0;
}
if(node.isWord){//此节点本身就是单词，求和
sum+=node.value;
}
if(node.nexts.keySet().size()>0){//节点还有子节点
for(Character key :node.nexts.keySet()){
sum+=value(node.nexts.get(key));//递归求和
}
}
return sum;
}
替换
一段文字内替换所有以
Trie中存储的单词
的单词
Example
Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
步骤：
- 构造Trie
- 将句子拆分成单词
- 将拆分的单词一个个的去Trie中查找，找到便替换
private String replaceWords(TrieNode root,String[] words){
StringBuilder stringBuilder=new StringBuilder();
for(int i=0;i<words.length;i++){
stringBuilder.append(replaceWords(root,words[i])).append(" ");//将拆分的单词一个个的去Trie中查找，找到便替换
}
stringBuilder.deleteCharAt(stringBuilder.length()-1);
return stringBuilder.toString();
}
private String replaceWords(TrieNode root,String word){
TrieNode node=root;
StringBuilder stringBuilder=new StringBuilder();
for(int i=0;i<word.length();i++){
if(node.nexts.get(word.charAt(i))==null){//没有此单词的前缀
return word;
}else{
stringBuilder.append(word.charAt(i));
if(node.nexts.get(word.charAt(i)).isWord){//找到了单词的替换
return stringBuilder.toString();
}else{
node=node.nexts.get(word.charAt(i));//查找下一层
}
}
}
return stringBuilder.toString();
}
模糊查找
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
步骤：
- 构建字典
- 每个字符在Trie中查找，碰到模糊词汇使用递归
public boolean search(String word) {
return search(word,root);
}
public boolean search(String word,TrieNode root){
if(word.length()==0){//每个字符都找完了，看最后一个节点是不是单词
return root.isWord;
}
char c=word.charAt(0);
if(c!='.'){//非模糊
if(root.nexts.get(c)==null){//字符不匹配查找失败
return false;
}else{//字符匹配，递归看子节点
return search(word.substring(1),root.nexts.get(c));
}
}else{//模糊
for(char ch :root.nexts.keySet()){//跳过模糊字符，查找下一字符
if(search(word.substring(1),root.nexts.get(ch)))//注意成功返回，失败一次不代表全部失败
return true;
}
return false;//全部失败
}
}
求最大异或值
在给定的数组中两两项异或，找出最大的异或值。
性质：
有 a ^ b = x
则 a ^ x = b ， b ^ x = a
一个数的大小如何判断？从高位向低位走，先遇到不为0的数最大（1000 、0100），若高位相同继续向低位走（1000 、 1100）。
思路：
- 将整数转成二进制存入Trie
- 由于求最大值，所以从高位向低位存储
- 循环数组
- 假设项为a，存在于Trie中最大的异或值为x，a、Trie已知
- 若想x最大，则x的每一位都为1，但不可能
- 用a的每一位去异或1（性质），求得b的这一位，若b的这一位在Trie中，则最大的x这一位确实存在，否则下一位
- 所有位都走完，求得a在Trie中的最大异或值。
- 循环数组完毕，找出最大的异或值
由于存储的节点只有0、1所以修改TrieNode结构
class TrieNode{
TrieNode[] children;
public TrieNode(){
children = new TrieNode[2];
}
}
构造Trie
private void buildTrie(int[] nums,TrieNode root){
for(int num:nums){
TrieNode node=root;
for(int i=31;i>=0;i--){
int bit=(num >> i)&1;//与1是为了只求一位
if(node.children[bit]==null){
node.children[bit]=new TrieNode();
}
node=node.children[bit];
}
}
}
遍历查找最大异或值
public int findMaximumXOR(int[] nums,TrieNode root) {
int max=0;
for(int num :nums){
TrieNode node=root;
int res=0;
for(int i=31;i>=0;i--){
int bit=(num >> i)&1;
if(node.children[bit^1]!=null){//找到b的这一位
res+=1<<i;//累加x的这一位
node=node.children[bit^1];//去b的下一位找最大值
}else{//没找到b的这一位，如思路中的x的每一位不可能都为1
node=node.children[bit];
}
//由于是从高位开始查找的，所以先找到的1，一定是最大的
}
max=Math.max(res,max);
}
return max;
}
矩阵中查找单词
给定矩阵，判断输入的单词是否在矩阵中。
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
矩阵中字符可以横向纵向组合成单词
思路：
- 构建要查找单词的Trie
- 遍历矩阵中的每一项
- 让每一项上下左右构成单词后去Trie中查找（递归）
public List<String> findWords(char[][] board, String[] words) {
Trie trie=new Trie();
for(String s: words){
trie.insert(s);
}
int y=board.length;
int x=board[0].length;
boolean[][] visited=new boolean[y][x];//记录是否走过此路
for(int i=0;i<x;i++){
for(int j=0;j<y;j++){//遍历所有的点，这里还不是递归
dfs(board,visited,"",i,j,trie);
}
}
return new ArrayList<String>(res);
}
public void dfs(char[][] board,boolean[][] visited,String str,int x,int y,Trie trie){
if(x<0||x>=board[0].length||y<0||y>=board.length) return;//所要查询的位置越界
if(visited[y][x])return;//已经走过该路
str+=board[y][x];//新字符串
if(!trie.startWith(str)) return;//如果没有此前缀，不必浪费时间
if(trie.search(str)){//在矩阵中找到该词，加入结果
res.add(str);
}
visited[y][x]=true;//记录当前已走
dfs(board,visited,str,x-1,y,trie);//横向查找
dfs(board,visited,str,x+1,y,trie);
dfs(board,visited,str,x,y-1,trie);//纵向查找
dfs(board,visited,str,x,y+1,trie);
visited[y][x]=false;//真个矩阵走完后，重置状态为下一次做准备
}
回文
在给出的单词组中，找出可以组成回文的两个单词组。
LeetCode
Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]
Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
class TrieNode {
HashMap<Character,TrieNode> children;
int index;
List<Integer> list;
public TrieNode(){
children=new HashMap<Character,TrieNode>();
index=-1;
list=new ArrayList<Integer>();
}
}
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
TrieNode root=new TrieNode();
for(int i=0;i<words.length;i++) addWord(root,words[i],i);
for(int i=0;i<words.length;i++) search(words[i],i,root,res);
return res;
}
private void addWord(TrieNode root,String word,int index){
TrieNode node=root;
for(int i=word.length()-1;i>=0;i--){//倒序插入，正序查找
if(node.children.get(word.charAt(i))==null){
node.children.put(word.charAt(i),new TrieNode());
}
if(isPalindrome(word,0,i)) node.list.add(index);//单词内部回文，node不仅仅属于此word，所以要添加到list
node=node.children.get(word.charAt(i));
}
node.list.add(index);//此单词结束，不代表到达叶子节点
node.index=index;//记录此节点为单词
}
private void search(String word,int index,TrieNode root,List<List<Integer>> res){
for(int i=0;i<word.length();i++){
if(root.index>=0&&root.index!=index&&isPalindrome(word,i,word.length()-1)){
//倒序插入，正序查找，找到的节点为单词且不是自己，证明到此节点root单词与单词前半部分回文，如果单词后半部分回文，则两单词一定回文
res.add(Arrays.asList(index,root.index));
}
root=root.children.get(word.charAt(i));
if(root==null){//查找结束
return;
}
}
for(int i:root.list){//最后一个节点一定是单词，同root.index>=0
if(index==i) continue;//去除自己，同root.index!=index
res.add(Arrays.asList(index,i));//由于是最后一个节点，所以没有后半部分
}
//单词A、B，回文不一定AB回文且BA回文，只要其中一项即可，勿陷入盲区
}
private boolean isPalindrome(String word,int start,int end){
while(start<end){
if(word.charAt(start++)!=word.charAt(end--)) return false;
}
return true;
}
}
