We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Ransom Note

Difficulty: Easy

Problem Description

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.

Key Insights

  • The task requires checking if the magazine contains enough letters to form the ransomNote.
  • Each letter in the magazine can only be used once, so we need to count the occurrences of each letter.
  • A hash table (or dictionary) can efficiently store and count the occurrences of letters.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of ransomNote and m is the length of magazine.
Space Complexity: O(1), since the hash table will store a fixed number of characters (26 lowercase letters).

Solution

The solution involves using a hash table to count the occurrences of each character in the magazine. We then iterate over the characters in the ransomNote and check if each character can be found in the hash table with a sufficient count. If we find any character in ransomNote that is either not in the hash table or has a count of zero, we return false. If we can check all characters successfully, we return true.

Code Solutions

def canConstruct(ransomNote: str, magazine: str) -> bool:
    # Create a dictionary to count occurrences of each letter in magazine
    letter_count = {}
    
    # Count each character in magazine
    for letter in magazine:
        if letter in letter_count:
            letter_count[letter] += 1
        else:
            letter_count[letter] = 1
    
    # Check if we can construct ransomNote
    for letter in ransomNote:
        if letter in letter_count and letter_count[letter] > 0:
            letter_count[letter] -= 1  # Use this letter
        else:
            return False  # Letter not available or used up
            
    return True
← Back to All Questions