Ransom Note

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

• Learning Python: From Zero to Hero
• Algorithms Problem Solving Series
• Stack Data Structure
• Queue Data Structure
• Linked List
• Tree Data Structure

Have fun, keep learning, and always keep coding!

My Twitter and Github