Ransom Note

easy LeetCode #383

hash-table string counting

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.

Example 1:
Input: ransomNote = "a", magazine = "b"
Output: false
Explanation: The magazine contains only 'b', but ransomNote needs 'a'. Cannot construct.

Example 2:
Input: ransomNote = "aa", magazine = "ab"
Output: false
Explanation: The magazine contains one 'a' and one 'b', but ransomNote needs two 'a's. Not enough 'a's.

Example 3:
Input: ransomNote = "aa", magazine = "aab"
Output: true
Explanation: The magazine contains two 'a's and one 'b'. RansomNote needs two 'a's, which are available.

Constraints

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

Complexity

Show Complexity

Time: O(m + n)
Space: O(1)

Hints

Show Hints

Pattern: Character frequency counting with hash map
Approach: Use a hash map or array of size 26 to count letter frequencies in magazine, then verify each letter in ransomNote has sufficient count
Complexity: Count characters in magazine, then check if ransomNote can be satisfied

Solutions

Show PY Solution

from collections import defaultdict


def solution(ransomNote: str, magazine: str) -> bool:
    m = defaultdict(int)

    for c in ransomNote:
        m[c] += 1

    for c in magazine:
        if c in m:
            m[c] -= 1
            if m[c] == 0:
                del m[c]

    return len(m) == 0

    # mr = defaultdict(int)
    # mm = defaultdict(int)
    #
    # for c in ransomNote:
    #     mr[c] += 1
    #
    # for c in magazine:
    #     mm[c] += 1
    #
    # ans = True
    # for k, v in mr.items():
    #     if v > mm[k]:
    #         return False
    #
    # return ans