## DEV Community

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

## Resources

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.

Amr Monier

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