Home

Ransom Note

Magazine Photo by Rhema Kallianpur

This post is part of the Algorithms Problem Solving series.

Problem description

This is the Ransom Note problem. The description looks like this:

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Examples

# ransomNote = "a", magazine = "b"
# => false

# ransomNote = "aa", magazine = "ab"
# => false

# ransomNote = "aa", magazine = "aab"
# => true

Solution

def can_construct(ransom_note, magazine):
    if ransom_note == '':
        return True

    if magazine == '':
        return False

    letters_counter = {}

    for letter in magazine:
        if letter in letters_counter:
            letters_counter[letter] += 1
        else:
            letters_counter[letter] = 1

    for char in ransom_note:
        if char not in letters_counter or letters_counter[char] == 0:
            return False

        letters_counter[char] -= 1

    return True

Resources

Patreon Become a Patron Coffee icon Buy me a coffee