leetcode刷题 | 关于前缀树的题型总结

题目链接

208. 实现 Trie (前缀树) - 力扣（LeetCode）

648. 单词替换 - 力扣（LeetCode）

676. 实现一个魔法字典 - 力扣（LeetCode）

820. 单词的压缩编码 - 力扣（LeetCode）

677. 键值映射 - 力扣（LeetCode）

421. 数组中两个数的最大异或值 - 力扣（LeetCode）

实现 Trie (前缀树)

前缀树是一种数据结构，一般用于高效存储和检索字符串的键。

class Trie {
    TreeNode root;
    class TreeNode{
        TreeNode[] next;
        boolean isEnd;
        public TreeNode(){
            // 子节点的指针数组，长度为26，可以包含所有的小写字母
            next = new TreeNode[26];
            // 表示是否为字符串的结尾
            this.isEnd = false;
        }
    }
    public Trie() {
        // 初始化
        root = new TreeNode();
    }
    
    public void insert(String word) {
        TreeNode cur = root;
        // 将当前字符串插入到前缀树中
        for(char c : word.toCharArray()){
            // 如果不存在那么新建一个前缀树节点，进行插入
            // 如果存在那么指针移动到下一个节点，处理下一个字符
            if(cur.next[c-'a'] == null) cur.next[c-'a'] =new TreeNode();
            cur = cur.next[c-'a'];
        }
        // 插入完毕标记到了结尾
        cur.isEnd = true;
    }
    
    public boolean search(String word) {
        TreeNode cur = root;
        for(char c: word.toCharArray()){
            // 如果当前节点不存在，那么直接返回false，前缀树中没有这个字符串
            if(cur.next[c-'a'] == null) return false;
            cur = cur.next[c-'a'];// 继续处理下一个字符节点
        }
        return cur.isEnd; //返回是否结束，如果字符串没有结束那么也不包含该字符串
    }

    public boolean startsWith(String prefix) {
        TreeNode cur = root;
        for(char c: prefix.toCharArray()){
            // 如果不存在，那么不存在该前缀
            if(cur.next[c-'a'] == null) return false;
            cur = cur.next[c-'a'];
        }
        return true;
    }
}

单词替换

使用前缀树构造一颗字典树，将所有的词根都放入到前缀树中，遍历句子中的每一个单词，对单词在字典中进行词根搜索，找到对应的词根，用找到的词根换当前单词

class Solution {
    TrieNode root = new TrieNode();
    class TrieNode{
        TrieNode[] next ;
        boolean isEnd;
        public TrieNode(){
            next = new TrieNode[26];
            isEnd = false;
        }
    }
    // 将词根插入到字典树(前缀树)中
    public void insert(String word,TrieNode root){
        TrieNode node = root;
        for(char c:word.toCharArray()){
            if(node.next[c-'a'] == null) node.next[c-'a']=new TrieNode();
            node = node.next[c-'a'];
        }
        node.isEnd = true;
    }
	// 查找字符串中的词根
    public boolean search(TrieNode root,String word){
        TrieNode node = root;
        for(char c:word.toCharArray()){
            if(node.isEnd == true) break;
            if(node.next[c-'a'] == null) return false;
            node = node.next[c-'a'];
        }
        return true;
    }
	
    // 进行替换
    public String replace(String word,TrieNode root){
        StringBuilder sb = new StringBuilder();
        TrieNode node = root;
        for(char c: word.toCharArray()){
            // 如果当前节点为末尾，跳出循环，返回当前找到的词根
            if(node.isEnd) break;
            // 处理下一个节点
            node = node.next[c-'a'];
            // 将当前词根加入到字符串中
            sb.append(c);
        }
        return sb.toString();
    }
    public String replaceWords(List<String> dictionary, String sentence) {
        // 插入词根
        for(String s: dictionary) insert(s,root);
        String[] split = sentence.split(" ");
        for (int i = 0; i < split.length; i++) {
            // 进行替换
            if (search(root,split[i])) split[i] = replace(split[i],root);
        }
        StringBuilder sb = new StringBuilder();
        for(String s: split){
            sb.append(s+" ");
        }
        sb.deleteCharAt(sb.length()-1);
        return sb.toString();
    }
}

实现一个魔法字典

class MagicDictionary {
	class Trie {
    	boolean isFinished;
    	Trie[] child;

 	   public Trie() {
 	       isFinished = false;
	        child = new Trie[26];
 	   }
	}
    Trie root;

    public MagicDictionary() {
        root = new Trie();
    }

    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            Trie cur = root;
            for (int i = 0; i < word.length(); ++i) {
                char ch = word.charAt(i);
                int idx = ch - 'a';
                if (cur.child[idx] == null) {
                    cur.child[idx] = new Trie();
                }
                cur = cur.child[idx];
            }
            cur.isFinished = true;
        }
    }

    public boolean search(String searchWord) {
        return dfs(searchWord, root, 0, false);
    }

    private boolean dfs(String searchWord, Trie node, int pos, boolean modified) {
        if (pos == searchWord.length()) {
            return modified && node.isFinished;
        }
        int idx = searchWord.charAt(pos) - 'a';
        if (node.child[idx] != null) {
            if (dfs(searchWord, node.child[idx], pos + 1, modified)) {
                return true;
            }
        }
        if (!modified) {
            for (int i = 0; i < 26; ++i) {
                if (i != idx && node.child[i] != null) {
                    if (dfs(searchWord, node.child[i], pos + 1, true)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

我觉得遍历查找的方式就很好了，前缀树多少有点绕圈子b(￣▽￣)d

class MagicDictionary {
    String[] words;
    /** Initialize your data structure here. */
    public MagicDictionary() {

    }
    
    public void buildDict(String[] dictionary) {
        words = dictionary;
    }
    
    public boolean search(String searchWord) {
        for(String s: words){
            // 标记一个字符串中字符与词根中字符不同的个数
            int diff = 0;
            if(s.length() != searchWord.length()) continue;
            for(int i = 0;i<searchWord.length();i++){
                if(s.charAt(i) != searchWord.charAt(i)) {
                    diff++;
                    // 大于1个那么直接跳出循环，返回false，不能够转换一次就和词根一样
                    if(diff > 1) break;
                }
            }
            // 如果为1，那么可以转换
            if(diff == 1) return true;
        }
        return false;
    }
}

单词的压缩编码

保留所有不是其他单词后缀的单词

将所有的字符倒着插入到前缀树中，如果找到了

class Solution {
    public int minimumLengthEncoding(String[] words) {
        TrieNode root = new TrieNode();
        HashMap<TrieNode,Integer> map = new HashMap(); 
        for(int i = 0;i<words.length;i++){
            String s = words[i];
            TrieNode node = root;
            for(int j = s.length()-1;j>=0;j--){
                // 倒着插入前缀树
                // 得到当前节点
                node = node.get(s.charAt(j));
            }
            // 将节点和当前字符的下标存入到map中
            map.put(node,i);
        }
        int res = 0;
        for(TrieNode node : map.keySet()){
            // 遍历map
            // 如果当前节点的count = 0，说明为叶子节点，叶子结点就是不是后缀的单词
            // 取出map中的保存的下标，将所有不是后缀的单词长度相加
            // +1 是 +#
            if(node.count == 0) res+=words[map.get(node)].length()+1;
        }     
        return res;
    }
    class TrieNode{
        TrieNode[] children;
        int count;
        public TrieNode(){
            children = new TrieNode[26];
            count = 0;
        }
        public TrieNode get(char c){
            if(children[c-'a'] == null){
                // 前缀树中没有当前字符，创建前缀树节点
                children[c-'a'] = new TrieNode();
                count ++; // 长度为1
            }
            // 如果前缀树中存在当前字符，那么该字符为某一个单词的后缀，直接返回当前节点，当前节点的值为1
            // 后续判断中会用到
            return children[c-'a']; // 返回当前节点
        }
    }
}

键值映射

class MapSum {
    TrieNode root;
    HashMap<String,Integer> map;

    public MapSum() {
        root = new TrieNode();
        map = new HashMap();
    }
    
    // 插入
    public void insert(String key, int val) {
        // 当前值-map中包含该键的值，增量
        int d = val-map.getOrDefault(key,0);
        // 将key和val存入到map
        map.put(key,val);
        TrieNode cur = root;
        for(char c : key.toCharArray()){
            // 遍历key的字符
            // 字符节点为空，新建一个节点
            if(cur.next[c-'a'] == null){
                cur.next[c-'a'] = new TrieNode();
            }
            // 继续处理下一个节点
            cur = cur.next[c-'a'];
            // 需要更新每个前缀对应的值
            // 把每一个节点都加增量，以便后续计算以某前缀开头所有key的和
            cur.val += d;
        }
    }
    // 以某前缀开头所有key的和
    public int sum(String prefix) {
        TrieNode cur = root;
       
        for(char c: prefix.toCharArray()){
            // 如果当前节点为空，那么没有前缀树中不存在该前缀，直接返回0
            if(cur.next[c-'a'] == null) return 0;
            cur = cur.next[c-'a'];
        }
        // 直接返回当前节点的值，就为和
        return cur.val;
    }
    class TrieNode{
        TrieNode[] next;
        int val;
        public TrieNode(){
            next = new TrieNode[26];
            val = 0;
        }

    }
}

这道题我也觉得HashMap最好用，直接使用哈希中封装好的函数👍

class MapSum {
    HashMap<String,Integer> map;
    /** Initialize your data structure here. */
    public MapSum() {
         map = new HashMap();
    }
    
    public void insert(String key, int val) {
        map.put(key,val);
    }
    
    public int sum(String prefix) {
        int res = 0;
        for(String s:map.keySet()){
            if(s.startsWith(prefix)) res += map.get(s);
        }
        return res;
    }
}

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

异或就是当位两个数的值不同才为1，所以需要尽量找到一个与当前位不同的数

先确定高位，再确定低位，才能保证最大 ，接着一位一位去确定这个数位的大小

class Solution {
   class TrieNode{
        TrieNode[] next;
        public TrieNode(){
            next = new TrieNode[2];
        }
    }
    TrieNode root = new TrieNode();
    
    public int findMaximumXOR(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int num:nums){
            inster(num);
            max = Math.max(max,maxOR(num));
        }
        return  max;
    }
    public void inster(int num){
        TrieNode node = root;
        // 倒着取出，先得到最低位
        for(int i = 31;i>=0;i--){
            int d = num >> i & 1; //取出第i位的数
            if (node.next[d] == null) node.next[d] = new TrieNode();
            node = node.next[d];
        }
    }
    public int maxOR(int num){
        TrieNode node = root;
        int res = 0;
        for (int i = 31;i>=0;i--){
            int d = num >>i & 1;
            // 由于异或要最大，则尽量走与 num 当前二进制位 d 相反的一位，
            // 如果相反的一位为空，则只好走相同的一位了。
            int opposite = (d==0)?  1 : 0; //为了让异或结果最大，选择不同的二进制进行异或
            if (node.next[opposite] != null){
                res = res*2+opposite; //因为是二进制所以*2
                node = node.next[opposite];
            }else{
                //如果不存在这样的数，就先选择相同的
                res = res*2+d;
                node = node.next[d];
            }
        }
        return  num^res;
    }
    
}