EasyNo. 0383

Ransom Note — LeetCode 383 Python Solution

Pattern
Hash Map
Topics
Hash Table, String, Counting
On study lists
Grind 75 and Top Interview 150
Reading time
2 min

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

PythonSolution
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

Time
O(m + n)
Space · auxiliary
O(C)

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

Related problems
No.ProblemDifficulty
0387First Unique Character in a StringEasy
0299Bulls and CowsMedium
0451Sort Characters By FrequencyMedium
0692Top K Frequent WordsMedium
0767Reorganize StringMedium
0811Subdomain Visit CountMedium

Frequently asked questions

How hard is LeetCode 383. Ransom Note?

LeetCode 383. Ransom Note is rated Easy on LeetCode.

What is the time complexity of LeetCode 383. Ransom Note?

The Python solution on this page runs in O(m + n).

What is the space complexity of LeetCode 383. Ransom Note?

The Python solution on this page uses O(C) auxiliary space.

What topics does LeetCode 383. Ransom Note cover?

LeetCode 383. Ransom Note is tagged Hash Table, String and Counting on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.