Ransom Note
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!