[LeetCode]Map Sum Pairs

题目描述:

LeetCode 677. Map Sum Pairs

Implement a MapSum class with insert, and sum methods.

For the method insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.

Example 1:

Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5

题目大意:

设计一个数据结构MapSum,支持insert和sum操作。

insert(key, val):向MapSum中插入一个key,对应一个val(当key存在时,替换对应的val)

sum(prefix):求MapSum中对应前缀为prefix的所有key的val之和

解题思路:

字典树(Trie)

TrieNode包含属性:sum(当前节点子树的和),val(当前节点的值)

insert操作:向字典树中插入节点,并将沿途节点记录下来。更新途经节点的sum值

sum操作:直接返回前缀对应节点的sum值

Python代码:

class TrieNode:
    # Initialize your data structure here.
    def __init__(self):
        self.children = dict()
        self.sum = 0
        self.val = 0

class MapSum(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, key, val):
        """
        :type key: str
        :type val: int
        :rtype: void
        """
        node = self.root
        nodes = []
        for letter in key:
            child = node.children.get(letter)
            if child is None:
                child = TrieNode()
                node.children[letter] = child
            nodes.append(child)
            node = child
        if node.val != val:
            delta = val - node.val
            node.val = val
            for node in nodes:
                node.sum += delta

    def sum(self, prefix):
        """
        :type prefix: str
        :rtype: int
        """
        node = self.root
        for letter in prefix:
            node = node.children.get(letter)
            if node is None: return 0
        return node.sum

# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)

 

本文链接:http://bookshadow.com/weblog/2017/09/17/leetcode-map-sum-pairs/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码