数据结构笔记总结(9.6)Trie字典树和字符串映射

Trie字典树和字符串映射

前面实现的Trie都是把它当成一个字符串的集合来使用,主要在Trie中添加或查询一个单词是否存在。

在查询方面上一小节通过一个LeetCode问题知道了还可以进行一定的字符串模式匹配,这一小节我们具体来看看当我们把Trie当成一个映射来使用的情况是怎样的?

677. 键值映射

实现一个 MapSum 类里的两个方法,insert 和 sum。

对于方法 insert,你将得到一对(字符串,整数)的键值对。字符串表示键,整数表示值。如果键已经存在,那么原来的键值对将被替代成新的键值对。

对于方法 sum,你将得到一个表示前缀的字符串,你需要返回所有以该前缀开头的键的值的总和。

示例 1:

解题模板:

class MapSum {

    /** Initialize your data structure here. */
    public MapSum() {
        
    }
    
    public void insert(String key, int val) {
        
    }
    
    public int sum(String prefix) {
        
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */

简单分析

主要处理两个问题,第一个点就是之前所实现的Trie的node中并不包含Value值,现在我们要包含一个Value值。

第二点就是我们基于一个prefix,基于一个前缀来查找在Trie中所有包含这个前缀的所有词对应的Value和,这也是一个递归遍历的过程。

代码实现

import java.util.TreeMap;

public class MapSum {

    private class Node{

        public int value;
        public TreeMap next;

        public Node(int value){
            this.value = value;
            next = new TreeMap<>();
        }

        public Node(){
            this(0);
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public MapSum() {

        root = new Node();
    }

    public void insert(String key, int val) {

        Node cur = root;
        for(int i = 0 ; i < key.length() ; i ++){
            char c = key.charAt(i);
            if(cur.next.get(c) == null)
                cur.next.put(c, new Node());
            cur = cur.next.get(c);
        }
        cur.value = val;
    }

    public int sum(String prefix) {

        Node cur = root;
        for(int i = 0 ; i < prefix.length() ; i ++){
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null)
                return 0;
            cur = cur.next.get(c);
        }

        return sum(cur);
    }

    private int sum(Node node){

        int res = node.value;
        for(char c: node.next.keySet())
            res += sum(node.next.get(c));
        return res;
    }
}

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(9.6)Trie字典树和字符串映射

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多