Ransom Note | LeetCode 383 | Python | Solution

LeetCode 383

Problem Overview

Ransom Note is a pretty common programming problem. The problem description is concise and understandable.

So, this problem says that we will be given two strings (ransomNote and magazine). In short, we have to return True if all the characters of the ransomNote are in the magazine string. Otherwise, False.

For example:

ransomNote = 'eeeo'
magazine = 'leetcode'
# True

ransomNote = 'abc'
magazine = 'abad'

# False

Each character of the magazine string is allowed to be used once.

So, if ransomNote = ‘aa’ and magazine = ‘a’, the answer will be False.

Coding Part

We can solve this problem in many ways. Let’s see one of them.

To solve this problem, we will use two built-in Python functions. These two are: set and count. In short, the set is for removing duplicate elements. Using this function, we will run a loop on ransomNote, so that the loop can run on the duplicate words only once.

Inside the loop, we will check one thing. If the count of any letter in ransomNote is greater than the magazine’s letter, then we will return False. Because in that case, it’s not possible to construct a ransomNote from that magazine.

If our checking successfully reaches the end, we can assume that all the letters of ransomNote are in the magazine. So, we will return True.

Let’s see the code.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:

        for let in set(ransomNote):
            
            if ransomNote.count(let) > magazine.count(let):
                return False
        
        return True

Second Solution

Another way we can solve this problem. This way, time complexity will be better than the previous solution. So the time and space complexity will be O(n). Let’s see the solution.

In this way, we will use HashTable. In that HashTable, we will store the character frequency of the magazine. And then, we will run a loop on the ransom string. In this loop, we will check three things:

1. If the character of the ransom note is not in the HashTable, we will return False.
2. If the same character previously appeared, there is a chance that the frequency was reduced to 0. In this case, we will also return False.
3. Otherwise, we will reduce the frequency by 1

After the loop, we will return True. Let’s see the code.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        
        mag = Counter(magazine)
        
        for c in ransomNote:
            
            if c not in mag:
                return False
            elif mag[c] == 0:
                return False
            else:
                mag[c] -= 1
        
        return True

I hope you got the idea of the problem and solution.
Happy Learning.
Happy Coding.