loading...
Cover image for Algorithms Problem Solving: Ransom Note

Algorithms Problem Solving: Ransom Note

teekay profile image TK Originally published at leandrotk.github.io ・2 min read

Algorithms Problem Solving Series (23 Part Series)

1) Algorithms Problem Solving: Jewels and Stones 2) Algorithms Problem Solving: Ransom Note 3 ... 21 3) Algorithms Problem Solving: Sum of nodes 4) Algorithms Problem Solving: Subtract product and sum 5) Algorithms Problem Solving: Cloned Binary Tree 6) Algorithms Problem Solving: Group the people 7) Algorithms Problem Solving: Equal Reversed Arrays 8) Algorithms Problem Solving: Even Number of Digits 9) Algorithms Problem Solving: Reduce to zero 10) Algorithms Problem Solving: Deepest Leaves Sum 11) Algorithms Problem Solving: Tree to greater sum 12) Algorithms Problem Solving: to Lower case 13) Algorithms Problem Solving: Balanced Strings 14) Algorithms Problem Solving: Number of students 15) Algorithms Problem Solving: Destination City 16) Algorithms Problem Solving: Maximum 69 Number 17) Algorithms Problem Solving: Shuffle the array 18) Algorithms Problem Solving: Insert into Binary Search Tree 19) Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal 20) Algorithms Problem Solving: Odd in Matrix 21) Algorithms Problem Solving: Sort the Matrix Diagonally 22) Algorithms Problem Solving: Discount for prices 23) Algorithms Problem Solving: Running Array Sum

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

Algorithms Problem Solving Series (23 Part Series)

1) Algorithms Problem Solving: Jewels and Stones 2) Algorithms Problem Solving: Ransom Note 3 ... 21 3) Algorithms Problem Solving: Sum of nodes 4) Algorithms Problem Solving: Subtract product and sum 5) Algorithms Problem Solving: Cloned Binary Tree 6) Algorithms Problem Solving: Group the people 7) Algorithms Problem Solving: Equal Reversed Arrays 8) Algorithms Problem Solving: Even Number of Digits 9) Algorithms Problem Solving: Reduce to zero 10) Algorithms Problem Solving: Deepest Leaves Sum 11) Algorithms Problem Solving: Tree to greater sum 12) Algorithms Problem Solving: to Lower case 13) Algorithms Problem Solving: Balanced Strings 14) Algorithms Problem Solving: Number of students 15) Algorithms Problem Solving: Destination City 16) Algorithms Problem Solving: Maximum 69 Number 17) Algorithms Problem Solving: Shuffle the array 18) Algorithms Problem Solving: Insert into Binary Search Tree 19) Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal 20) Algorithms Problem Solving: Odd in Matrix 21) Algorithms Problem Solving: Sort the Matrix Diagonally 22) Algorithms Problem Solving: Discount for prices 23) Algorithms Problem Solving: Running Array Sum

Posted on May 30 by:

teekay profile

TK

@teekay

Sharing knowledge https://leandrotk.github.io/tk

Discussion

markdown guide
 

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
 

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.

 

That makes sense. Thanks for sharing!

 

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
 

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
 

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.