Ransom Note

Problem

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.

Thought Process

• Count the number of distinct characters appearing in the note

Solution

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        dic = {}
        
        for letter in ransomNote:
            if letter not in dic:
                dic[letter] = 0
            dic[letter]+=1
        
        for i in magazine:
            if i in dic:
                dic[i]-=1
                if dic[i] == 0:
                    del dic[i]
        if len(dic) == 0:
            return True
        else:
            return False
                

Time Complexity

• Time: O(n)

• Space: O(1) because hash set is bounded by 26 characters