Leetcode!
  • LeetCode!
  • My personal guide to Leetcode
  • Array
    • 11. Container With Most Water
    • 15. 3Sum
    • 219. Contains Duplicate II
    • 238. Product of Array Except Self
    • 245. Shortest Word Distance III
    • 392. Is Subsequence
    • 442. Find All Duplicates in an Array
    • 561. Array Partition I
    • 661. Image Smoother
    • 697. Degree of an Array
    • 723. Candy Crush
    • 832. Flipping an Image
  • Backtracking
    • 294. Flip Game II
    • 401. Binary Watch
    • 1079. Letter Tile Possibilities
  • Binary Search
    • 744. Find Smallest Letter Greater Than Target
    • 852. Peak Index in a Mountain Array
  • String
    • 6. ZigZag Conversion
    • 17. Letter Combinations of a Phone Number
    • 38. Count and Say
    • 521. Longest Uncommon Subsequence I
    • 544. Output Contest Matches
    • 937. Reorder Data in Log Files
  • Design
    • 251. Flatten 2D Vector
    • 281. Zigzag Iterator
  • Hash Table
    • 1. Two Sum
    • 508. Most Frequent Subtree Sum
    • 884. Uncommon Words from Two Sentences
    • 734. Sentence Similarity
  • Linked List
    • 2. Add Two Numbers
  • Unsorted
    • 917. Reverse Only Letters
  • Math
    • 43. Multiply Strings
    • 462. Minimum Moves to Equal Array Elements II
    • 553. Optimal Division
    • 800. Similar RGB Color
  • Greedy
    • 406. Queue Reconstruction by Height
    • 861. Score After Flipping Matrix
  • Tree
    • 701. Insert into a Binary Search Tree
    • 897. Increasing Order Search Tree
  • Divide and Conquer
    • 53. Maximum Subarray
  • Dynamic Programming
    • 62. Unique Paths
    • 63. Unique Paths II
    • 64. Minimum Path Sum
    • 120. Triangle
    • 198. House Robber
    • 213. House Robber II
    • 303. Range Sum Query - Immutable
    • 518. Coin Change 2
    • 750. Number Of Corner Rectangles
    • 337. House Robber III
  • Depth first search
    • 841. Keys and Rooms
  • Trie
    • 677. Map Sum Pairs
  • Two pointer
    • 42. Trapping Rain Water
Powered by GitBook
On this page
  1. Trie

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

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

Previous841. Keys and RoomsNext42. Trapping Rain Water

Last updated 6 years ago