Today’s data structure is a hashmap. I have a lot more experience with this data structure. My confidence for today’s leetcode was higher than the previous day’s leetcode problem. Today I’m tackling another easy leetcode problem. I’m going to have to do these daily to increase my skills.

My language of choice for these problems is python. Python’s implementation of hashmaps are known as Dictionaries.

Hashmaps⌗

Also known as Hash Tables, organizes data so it can quickly look up values for a given key. Python’s dictionary documentation is a good reference for all of the methods available to use when dealing with dictionaries. When I use the term Dictionary, I’m referring to Hashmaps.

A hashmap defines a buckets for which a desired value can be placed into. The Hashmap allows a programmer to reference and use a value by a “human readable” key. The values are grabbed through a set of hashing functions that are used in tandem with hashmaps/hashtables. Big brained computer scientists have designed these hashing functions to grab the values, and to avoid hashing collisions.

Problem Statement⌗

In tody’s leetcode problem, given two strings ransomNote and magazine, return True if ransomNote can be constructed by using the letters from magazine. Return False if otherwise.

My first thought was to use two dictionaries to count the occurrence of each character in both strings. We must loop over each character of ransomNote and magazine, and count the number of times each letter, or character, appears in the string.

After the counts are determined, we can then loop over each dictionary item in ransomNote and see if the key exists in magazine. If it does not, we can return False right there, because there must be at least the same number of occurrences of keys in ransomNote to the keys in magazine.

def populateDict(input_string):
    input_dict = {}
    for letter in input_string:
        if letter not in input_dict.keys():
            input_dict[letter] = 1
        else:
            input_dict[letter] += 1
    return input_dict

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ransomDict = populateDict(ransomNote)
        magDict = populateDict(magazine)
        
        for key, value in ransomDict.items():
            if magDict.get(key, 0) < value:
                return False
        return True  

The ransomDict.items() line returns a tuple in the form of (key, value) for each item in the ransom dictionary. We are calling the magDict.get(key,0) to return 0 if the current key does not exist in magazine. In this case, we determined that the characters in magazine cannot recreate the string ransomNote.

My solution worked, but I will admit I feel like it’s doing a lot of looping. There must be a better more chad way to solve the problem.

Optimize⌗

It turns out Python has a Counter dictionary subclass that will automatically do what I was doing in my populateDict function. Learning new things everyday. So rather than using my mediocre function, I’m going to use this Counter class to count the occurrences of each character.

I wish I was big brained enough to think of this. The solution I found online is using the bitwise AND operator to compare both dictionaries. The bitwise AND operator will filter out things that are in magazine, but not in ransomNote, and it will give you a dictionary that matches the counts within ransomNote. Very elegant solution I found online:

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        note,mag = Counter(ransomNote), Counter(magazine)
        if note & mag == note: return True
        return False