Ransom Note (Leet code-383)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 383. This is a Leet code problem named Ransom Note We will solve it using python and it is the best space and time-optimized solution.

Question of Ransom Note

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Write a function that returns true if the ransom note can be created from the magazines; otherwise, it returns false. The function will be given an arbitrary ransom note string and another string containing letters from all the publications.

The condition is that you can only use each letter once in the magazine string once in your ransom message as given.

Example

Example 1

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2

Input: ransomNote = "aa", magazine = "ab"
Output: false

Constraints

1 <= ransomNote.length, magazine.length <= 10⁵
ransomNote and magazine consist of lowercase English letters.

Approach to solve Ransom Note

To solve this problem we will iterate each character of ransomNote and search that character in magazine. If the character is found in magazine then we delete the first found character. If the character is not found in magazine than we return false because after this we cannot create ransomNote from magazine.

Algorithm

This method performs the following steps for a given input array:

Check for base condition. check if ransomNote is grater than magazine if true return false.
Start for loop for each letter of ransomNote.
Check if letter is in magazine or not.
if found then then delete that character of magazine.
If not found return false.
End if statement
End for loop
In end, if every character of magazine is found in ransomNote then return True.

Python Code for Ransom Note

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        #check if ransomNote is grater than magazine if true return false
        if(len(ransomNote) > len(magazine)):            
            return False
                
        else:
            # search each letter of ransomNote in magzine
            for letter in ransomNote:
                if letter in magazine:
                    #if found then then delete that character of magazine
                    magazine = magazine.replace(letter, '', 1)
                else:
                    #otherwise return false
                    return False
            return True