[LeetCode/Python] 383. Ransom Note

📌 Problem

[LeetCode] 383. Ransom Note

📌 Solution

Solution 1: Use Counter

Code

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
		return Counter(ransomNote) <= Counter(magazine)

Solution 2: Use dictionary

Idea

• Use a dict cnt as the inventory (multiset) of characters in magazine
• Walk through ransomNote, decrement cnt[ch] for each char
• If any count drops below 0, it means you’re short on that char → return False immediately
• If you finish without negatives, you had enough of every char → return True

Code

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
		# Optional
        if len(ransomNote) > len(magazine):
            return False

        cnt = {}

        for ch in magazine:
            cnt[ch] = cnt.get(ch, 0) + 1

        for ch in ransomNote:
            cnt[ch] = cnt.get(ch, 0) - 1
            if cnt[ch] < 0:
                return False

        return True

Complexity

• Time Complexity: $O(n + m)$ where n = len(magazine), m = len(ransomNote)

• Space Complexity: $O(u)$ where u is the number of distinct chars in magazine