deepSWE.io

Ransom Note

Hashing

15 min

Problem Statement

Given two strings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.

Example

Example 1:

Input: ransomNote = "a", magazine = "b"

Output: false

Solution (Hash Map)

We can solve this by counting the characters in the magazine. Then, for each character in the ransom note, we check if it's available in our magazine counts and decrement the count.

Algorithm Steps

Create a hash map (or an array of size 26) to store the frequency of characters in the `magazine`.
Iterate through the `magazine` string and populate the frequency map.
Iterate through the `ransomNote` string.
For each character, check if it exists in the frequency map and its count is greater than 0.
If not, return `false`. Otherwise, decrement the character's count in the map.
If the loop completes, it means the ransom note can be constructed. Return `true`.

Ransom Note:

Magazine:

Magazine Character Counts

Ransom Note

Start. Count characters in the magazine.

Ransom Note Solution


class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        from collections import Counter
        
        ransom_counts = Counter(ransomNote)
        magazine_counts = Counter(magazine)
        
        for char, count in ransom_counts.items():
            if magazine_counts[char] < count:
                return False
        
        return True