383. Ransom Note Easy

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.

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

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

Example 3:
Input: ransomNote = "aa", magazine = "aab"
Output: true

Approach

Input: Two character lists ransomNote and magazine

Output: Determine if ransomNote can be constructed from the characters in magazine

This is a Hash Table problem.

Use a hash table to record the frequency of each letter in magazine.

Iterate through ransomNote and check the count of that letter in the hash table.

If it is 0 or does not exist, return false.

If all characters have sufficient counts, return true.

Implementation

python

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        cache = {}
        for ch in magazine:
            cache[ch] = cache.get(ch, 0) + 1  # get avoids manually checking if the key exists
        
        for ch in ransomNote:
            if cache.get(ch, 0) == 0:  # Default value 0, streamlines checking
                return False
            cache[ch] -= 1
        
        return True

javascript

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    const cache = {};

    for (let c of magazine) {
        cache[c] = (cache[c] || 0) + 1;
    }

    for (let c of ransomNote) {
        if (!cache[c]) return false;

        cache[c] -= 1;
    }

    return true;
};

Complexity Analysis

• Time Complexity: O(m + n) where m is length of ransomNote and n is length of magazine
• Space Complexity: O(1) space considering at most 26 lowercase English letters

Links

383. Ransom Note (English)383. 赎金信 (Chinese)