算法学习-字典树（持续更新中）

文章目录

- 一读就懂的储备知识
- - - 字典树模板
- 相关题目
- - - 208.实现Trie(前缀树)
    - 745.前缀和后缀搜索
    - 720.词典中最长的单词
    - 421.数组中两个数的最大异或值
    - 1707.与数组中元素的最大异或值
    - 211.添加与搜索单词
    - 剑指OfferII065.最短的单词编码
    - 648.单词替换

本文参考:
宫水三叶大佬的前缀树模板
@路漫漫我不畏的题解

一读就懂的储备知识

本文整理和汇总字典树的相关题目，记录自己的字典树刷题路径。

字典树又称为「前缀树」、「Trie树」，是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。

其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。因此针对前缀树中的节点来说，我们通常如下表示：

class TrieNode {
        boolean end; 
        TrieNode[] tns = new TrieNode[26];
    }

end表示是否为「单词结尾」，表示单词最后一条边的尾节点上置true，对tns数组中的TrieNode类指针判空，可以判断「是否存储了字符」。

可以变通的点如下：

boolean end语句不是前缀树中必须的，需要根据题目进行灵活变通，存储能够利于解题的数据结构。
数组的大小为26是只考虑了英文字母这个字符集，可以根据题目的字符集空间大小进行调整。
在insert建树操作（在下面字典树模板中）以后，需要针对题目设计search()以及startsWith()函数，实现对树查询得到结果。
字典树核心是一次建树，多次查询。每次单词的插入都是在前一次的树上进行生长。有些题目需要先将最终的树建立起来再查询，如648.单词替换，有些题目可以边建树边进行查询，如421.数组中两个数的最大异或值、1707.与数组中元素的最大异或值。

字典树是一棵多叉树（也可能是二叉树，取决于字符集空间大小），根节点的end域不具有信息，将其后的「一边一节点」视作一个单元，代表「该单词以后是否结束」，简单的示例图如下，其中忽略了空链接：

字典树模板

随着数据的不断插入，根据需要不断创建TrieNode节点，最后建立出一张完整的树进行查询。模板如下，还有一种数组的建树方式，但是并不如以下方式直观。

class Trie {
    class TrieNode {
        boolean end;
        TrieNode[] tns = new TrieNode[26];
    }
	
	//建立一棵前缀树，以root节点为起点
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }

	//插入
    public void insert(String s) {
    	//root是每次操作的开始，工作指针p初始化为root，后面单词搜索到哪里，p就跟到哪里
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) p.tns[u] = new TrieNode();
            p = p.tns[u]; 
        }
        p.end = true;
    }
	
	//搜索单词，如果不存在边直接return false, 最后节点的end表示是否有单词以此结尾
    public boolean search(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) return false;
            p = p.tns[u]; 
        }
        return p.end;
    }

	//搜索前缀,如果不存在边直接return false, 只要能搜索完s就表示是前缀
    public boolean startsWith(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) return false;
            p = p.tns[u]; 
        }
        return true;
    }
}

时间复杂度：插入和查找都为O(Len树的深度），例子中为单词的长度。

相关题目 208.实现Trie(前缀树)

class Trie {
    public class Node{
        boolean end;
        Node[] tns=new Node[26];
    }
    public Node root;
    public Trie() {
        root=new Node();
    }
    
    public void insert(String word) {
        Node p=root;
        for(int i=0;i
            int u=word.charAt(i)-'a';
            if(p.tns[u]==null) p.tns[u]=new Node();
            p=p.tns[u];
        }
        p.end=true;
    }
    
    public boolean search(String word) {
        Node p=root;
        for(int i=0;i
            int u=word.charAt(i)-'a';
            if(p.tns[u]==null) return false;
            p=p.tns[u];
        }
        return p.end;
    }
    
    public boolean startsWith(String prefix) {
        Node p=root;
        for(int i=0;i
            int u=prefix.charAt(i)-'a';
            if(p.tns[u]==null) return false;
            p=p.tns[u];
        }
        return true;
    }
}

745.前缀和后缀搜索

双字典树+双指针
根据前缀和后缀建立双字典树fronEnd、endFront，字典树节点中list存储以该节点为前缀的元素在数组中的下标。
建立字典树以后，f查询的过程中，根据前缀和后缀检索，得到两棵树对应节点上的下标数组prefNum、suffNum，通过双指针方法从后往前查找，找到相同下标的最大值。

class WordFilter {
    public class Node{
        ArrayList list=new ArrayList<>();
        Node[] next=new Node[26];
    }

    //两棵树的根结点
    Node frontEnd= new Node();
    Node endFront=new Node(); 

    //两棵树的建立过程
    public WordFilter(String[] words) {
        for(int i=0;i
            String s=words[i];

            Node p=frontEnd;
            Node k=endFront;
            for(int j=0;j
                int pidx=s.charAt(j)-'a';
                if(p.next[pidx]==null) p.next[pidx]=new Node();
                p=p.next[pidx];
                p.list.add(i);

                int kidx=s.charAt(s.length()-1-j)-'a';
                if(k.next[kidx]==null) k.next[kidx]=new Node();
                k=k.next[kidx];
                k.list.add(i);
            }
        }
    }
    
    public int f(String pref, String suff) {
        Node p=frontEnd;
        for(int i=0;i
            int prefidx=pref.charAt(i)-'a';
            if(p.next[prefidx]==null) return -1;
            p=p.next[prefidx];
        }
        List prefNum=p.list;
        
        Node k=endFront;
        for(int i=0;i
            //注意后缀为倒序
            int suffidx=suff.charAt(suff.length()-1-i)-'a';
            if(k.next[suffidx]==null) return -1;
            k=k.next[suffidx];
        }
        List suffNum=k.list;

        int prefNumLen=prefNum.size();
        int suffNumLen=suffNum.size();
        for(int i=prefNumLen-1,j=suffNumLen-1;i>=0&&j>=0;){
            int a=prefNum.get(i);
            int b=suffNum.get(j);
            if(a>b){
                i--;
            }else if(a
                j--;
            }else{
                return a;
            }
        }
        return -1;
    }
}

720.词典中最长的单词

构建字典树，记录每个单词结尾节点的end。
对于某个 words[i] 而言，其能成为「合法单词」的充要条件为：words[i] 的每个前缀节点都有end记录。
最后可以返回空并且考虑有多种情况，ans初始化为空字符串""。

class Solution {
    public class Node{
        boolean end;
        Node[] next=new Node[26];
    }
    Node root=new Node();
    public void insert(String s){
        Node p=root;
        for(char c:s.toCharArray()){
            int idx=c-'a';
            if(p.next[idx]==null) p.next[idx]=new Node();
            p=p.next[idx];
        }  
        p.end=true;
    }
    //满足逐步添加单词组成s的条件
    public boolean search(String s){
        Node p=root;
        for(char c:s.toCharArray()){
            int idx=c-'a';
            if(p.next[idx]==null||p.next[idx].end==false) return false;
            p=p.next[idx];
        }
        return p.end;
    }

    public String longestWord(String[] words) {
        //初始化ans为空的字符串
        String ans="";
        for(String s:words)insert(s);
        for(String s:words){
            int n=s.length();
            int m=ans.length();
            //两种剪枝条件
            //排除比答案小的s
            if(n0) continue;
            if(search(s)) ans=s;
        }
        return ans;
    }   
}

421.数组中两个数的最大异或值

我们需要先将 nums 中的数，从高位到低位以二进制的形式加入 Trie树中，开辟大小为2的Node数组，以指针序号表示，每个数字的树深最多为31。
然后对于每个数字，从高位到低位每次贪心的匹配与之不同的二进制位的分支，以此保证异或结果最大。

class Solution {
    public class Node{
        Node[] ns=new Node[2];
    }
    //建树
    Node root=new Node();
    public void add(int num){
        Node p=root;
        for(int i=30;i>=0;i--){
            int idx=(num>>>i)&1;
            if(p.ns[idx]==null) p.ns[idx]=new Node();
            p=p.ns[idx];
        }
    }
    //查找异或最大值
    public int getVal(int num){
        Node p=root;
        int ans=0;
        for(int i=30;i>=0;i--){
            int a=(num>>>i)&1,b=1-a;
            if(p.ns[b]!=null){
                ans|=(b<
                ans|=(a<
        int ans=0;
        for(int num:nums){
            add(num);
            int res=getVal(num);
            ans=Math.max(ans,num^res);
        }
        return ans;
    }
}

1707.与数组中元素的最大异或值

这种提前给定了所有询问的题目，我们可以运用离线思想（调整询问的回答顺序）进行求解，通常做法是对原数组排序，并用map存储原数组的下标对应关系。

对 nums 进行「从小到大」进行排序，对 queries 的第二维进行「从小到大」排序（排序前先将询问原本的下标映射关系用HashMap存下来）。
按照排序顺序处理所有的 queries[i]：
1. 在回答每个询问前，将小于等于 queries[i][1] 的数值存入字典树。由于我们已经事先对 nums 进行排序，因此这个过程只需要维护一个在 nums 上往右移动的指针一趟即可。
2. 然后利用贪心思路，查询每个 queries[i][0] 所能找到的最大值是多少，计算异或和，类似于421.数组中两个数的最大异或值
3. 找到当前询问在原询问序列的下标，将答案存入。

class Solution {
    public class Node{
        Node[]next=new Node[2];
    }
    Node root=new Node();
    public void add(int num){
        Node p=root;
        for(int i=30;i>=0;i--){
            int a=num>>>i&1;
            if(p.next[a]==null) p.next[a]=new Node();
            p=p.next[a];
        }
    }
    //直接返回最大异或值
    public int getVal(int num){
        Node p=root;
        int ans=0;
        for(int i=30;i>=0;i--){
            int a=num>>>i&1,b=1-a;
            if(p.next[b]!=null){
                ans|=b<
                ans|=a<
        int len1=nums.length;
        int len2=queries.length;
        HashMap map=new HashMap<>();
        for(int i=0;i
            map.put(queries[i],i);
        }
        //进行排序
        Arrays.sort(nums);
        Arrays.sort(queries,(o1,o2)->o1[1]-o2[1]);
        int loc=0;
        int[] ans=new int[len2];
        for(int[]q:queries){
            //加入的是nums中的值
            while(loc
                ans[map.get(q)]=-1;
            }else{
                ans[map.get(q)]=getVal(q[0]);
            }
        }
        return ans;
    }
}

211.添加与搜索单词

建树过程与模版类似，但由于加入了通配符.，所以其中搜索单词的过程采用dfs控制，分为确定的单词和通配符.两种情况。

class WordDictionary {
    public class Node{
        boolean isEnd;
        Node[]next=new Node[26];
    }
    Node root;
    public WordDictionary() {
        root=new Node();
    }
    
    public void addWord(String word) {
        Node p=root;
        for(int i=0;i
            int a=word.charAt(i)-'a';
            if(p.next[a]==null) p.next[a]=new Node();
            p=p.next[a];
        }
        p.isEnd=true;
    }
    
    public boolean search(String word) {
        return dfs(word,root,0);
    }
    public boolean dfs(String word,Node root,int index){
        if(index>=word.length()) return root.isEnd;
        if(word.charAt(index)!='.'){
            int a=word.charAt(index)-'a';
            if(root.next[a]==null) return false;
            return dfs(word,root.next[a],index+1);
        }else{
            for(Node n:root.next){
                if(n!=null&&dfs(word,n,index+1)) return true;
            }
        }
        return false;
    }
}

剑指OfferII065.最短的单词编码

后缀字典树+贪心
根据单词后缀建立字典树，如果能让某个单词尽可能多的包含别的单词（或者说别的单词是字典树的前缀），就能让长度最小。

考虑到最长的单词基本上都需要算入答案，因此先将words按长度降序，将其中不能构成前缀的单词插入字典树，并算入结果的长度。

class Solution {
    public class Node{
        Node[] next=new Node[26];
    }
    Node root=new Node();
    
    //构建字典树
    public void add(String s){
        Node p=root;
        for(int i=s.length()-1;i>=0;i--){
            int a=s.charAt(i)-'a';
            if(p.next[a]==null) p.next[a]=new Node();
            p=p.next[a];
        }
    }

    //判断s是否为字典树前缀
    public boolean startWith(String s){
        Node p=root;
        for(int i=s.length()-1;i>=0;i--){
            int a=s.charAt(i)-'a';
            if(p.next[a]==null) return false;
            p=p.next[a];
        }
        return true;
    }



    public int minimumLengthEncoding(String[] words) {
        int ans=0;
        Arrays.sort(words,(o1,o2)->o2.length()-o1.length());
        for(String s:words){
            if(!startWith(s)){
                add(s);
                ans+=s.length()+1;
            }
        }
        return ans;
    }
}

648.单词替换

简单理解为建立一棵前缀树，然后针对sentence中的所有单词s进行前缀替换，如果能被最前面end域为true的替换则替换，否则还是返回原来的s.

class Solution {
    public class Node{
        boolean isEnd;
        Node[] next=new Node[26];
    }
    Node root=new Node();

    public void add(String s){
        Node p=root;
        for(int i=0;i
            int a=s.charAt(i)-'a';
            if(p.next[a]==null) p.next[a]=new Node();
            p=p.next[a];
        }
        p.isEnd=true;
    }

    //查找最短的词根
    public String query(String s){
        Node p=root;
        for(int i=0;i
            int a=s.charAt(i)-'a';
            //这里的逻辑是，如果找不到词根，直接return s
            if(p.next[a]==null) break;
            if(p.next[a].isEnd==true) return s.substring(0,i+1);
            p=p.next[a];
        }
        return s;
    }

    public String replaceWords(List dictionary, String sentence) {
        StringBuilder sb= new StringBuilder();
        for(String s:dictionary){
            add(s);
        }
        for(String s:sentence.split(" ")){
            String res=query(s);
            sb.append(res).append(" ");
        }
        return sb.substring(0,sb.length()-1);
    }
}

暑期编程PK赛得CSDN机械键盘等精美礼品！

算法学习-字典树（持续更新中）

Java相关栏目本月热门文章