Ransom Note — LeetCode 383 Python Solution

The problem

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

Input

ransomNote = "a", magazine = "b"

Output

false

Python solution

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        cnt = Counter(magazine)
        for c in ransomNote:
            cnt[c] -= 1
            if cnt[c] < 0:
                return False
        return True

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 383. Ransom Note is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table and Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems