Leetcode – Ransom Note Solution in Python

Spread the love

Introduction

In this article, we’ll explore a Leetcode problem titled “Ransom Note”, and discuss various methods to solve this problem using Python.

Problem Statement

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.

Analyzing the Problem

The problem requires us to determine whether it’s possible to construct a given ransom note from a collection of letters from magazines. To solve this problem, we need to ensure that the magazine string contains at least as many occurrences of each character required by the ransom note string.

Let’s explore different approaches to solve this problem:

Approach 1: Using a Hash Table

One intuitive way to solve this problem is by using a hash table (or dictionary in Python) to keep track of the frequency count of each character in the magazine string. We can then iterate through each character in the ransom note and check if there are enough characters in the magazine to construct the ransom note.

def canConstruct(ransomNote: str, magazine: str) -> bool:
    char_count = {}
    
    # Count the frequency of each character in the magazine
    for char in magazine:
        char_count[char] = char_count.get(char, 0) + 1
        
    # Check if there are enough characters in magazine for ransomNote
    for char in ransomNote:
        if char_count.get(char, 0) == 0:
            return False
        char_count[char] -= 1
        
    return True

This approach has a time complexity of O(N + M), where N is the length of the ransom note, and M is the length of the magazine.

Approach 2: Using Collections Counter

Python has a built-in module called collections which has a Counter class. Counter is essentially a hash table (dictionary) subclass designed to count hashable objects. We can leverage Counter to solve this problem in a more concise way.

from collections import Counter

def canConstruct(ransomNote: str, magazine: str) -> bool:
    # Count the frequency of each character
    ransom_count = Counter(ransomNote)
    magazine_count = Counter(magazine)
    
    # Check if there are enough characters in magazine for ransomNote
    for char, count in ransom_count.items():
        if count > magazine_count[char]:
            return False
            
    return True

This approach has the same time complexity of O(N + M) as the first approach, but is cleaner due to the use of the Counter class.

Approach 3: Optimizing Space

If space is a concern, we can further optimize the first approach by using only one hash table to store the character counts of the magazine. We can then iterate through the ransom note, decrementing the count for each character and checking if it’s possible to construct the note.

def canConstruct(ransomNote: str, magazine: str) -> bool:
    char_count = {}
    
    # Count the frequency of each character in the magazine
    for char in magazine:
        char_count[char] = char_count.get(char, 0) + 1
    
    # Decrement counts and check as we iterate through ransomNote
    for char in ransomNote:
        if char_count.get(char, 0) <= 0:
            return False
        char_count[char] -= 1
        
    return True

This approach reduces the space complexity by using only one hash table instead of two.

Conclusion

In this article, we have delved into the Ransom Note problem on Leetcode and explored various approaches to solving it using Python. Utilizing hash tables (dictionaries) or the built-in Counter class are effective methods. It’s important to consider the trade-offs between readability, time complexity, and space complexity when choosing an approach to solve a problem.

Leave a Reply