DEV Community is a community of 756,027 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

TK

Posted on • Originally published at leandrotk.github.io

Algorithms Problem Solving: Ransom Note

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
``````

Discussion (6)

Ryan Palo

Have you heard about the `collections` module in the standard library? It's got a class called `Counter` available that is really useful in situations like this. Check out the docs

``````from collections import Counter

def can_build_ransom_note(message, magazine):
needed_letters = Counter(message)
available_letters = Counter(magazine)

for letter, count in needed_letters.items():
if available_letters[letter] < count:
return False

return True
``````
TK

I 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.

Ryan Palo

That makes sense. Thanks for sharing!

Jing Xue

Another solution:

``````    def can_construct(ransom_note, magazine):
for c in ransom_note:
prev_len = len(magazine)
magazine = magazine.replace(c, '', 1)
if len(magazine) == prev_len:
return False
return True
``````
TK

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.

AmrMonier

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 ?)

``````class RansomNote:
def __init__(self, note: str, mags: str) -> bool:
self.note = note
self.mags = mags
if self.checkValidInput():
if(self.canBeConstructed()):
print('Message Can Constructed')
else:
print('Can\'t be constructed')
else:
print('Can\'t be constructed')

def checkValidInput(self) -> bool:
if(len(self.mags) < len(self.note)):
return False
return True

def isInRansom(self, letter) -> bool:
pos = self.note.find(letter)
if pos != -1:
self.note = self.note[:pos] + self.note[pos+1:]
return True
else:
return False

def canBeConstructed(self) -> bool:
for letter in self.mags:
if len(self.note) == 0:
return True
else:
if(not self.isInRansom(letter)):
self.mags = self.mags.replace(letter, '')

return False
``````