> For the complete documentation index, see [llms.txt](https://programming.arora-aditya.com/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://programming.arora-aditya.com/leetcode/trie/677.-map-sum-pairs.md).

# 677. Map Sum Pairs

## Approach 1: Hash Map Counting

We can simply keep a track of the words and their counts. Once we're asked to check a prefix we can simply iterate over the keys and add up the counts one by one

```python
class MapSum(object):
    # https://leetcode.com/problems/map-sum-pairs/description/
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.di = {}

    def insert(self, key, val):
        """
        :type key: str
        :type val: int
        :rtype: void
        """
        self.di[key] = val


    def sum(self, prefix):
        """
        :type prefix: str
        :rtype: int
        """
        count = 0
        for i in self.di:
            if i.startswith(prefix):
                count += self.di[i]
        return count



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

```

> **Time Complexity:** *O(K^2), where K is the average length of the string*
>
> **Space Complexity:** O(N), where N is the number of words