This post is part of the Algorithms Problem Solving series. And it was originally published on TK's blog.
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
- Big-O Notation For Coding Interviews and Beyond
- Learn Python from Scratch
- Learn Object-Oriented Programming in Python
- Data Structures in Python: An Interview Refresher
- Data Structures and Algorithms in Python
- Data Structures for Coding Interviews in Python
- One Month Python Course
Top comments (6)
Have you heard about the
collections
module in the standard library? It's got a class calledCounter
available that is really useful in situations like this. Check out the docsI didn't know about this
Counter
class. It is awesome! But my idea with this whole algorithm series is to try to implement the algorithm without help from built-in methods or classes. Just the default data structures.Thanks for the note! I really liked this class.
That makes sense. Thanks for sharing!
Another solution:
Great, Jing!
This was very similar with my first solution. But I wanted to try a different solution without using the
replace
method. Just to challenge me.this my solution, i didn't want to match any character again if i already know that it's n't in the ransom note.
i think this would be a good solution in case the magazines string is huge.
but i have a question for huge strings (would it be better if we sorted the strings first ?)