383. Ransom Note
Learn how to efficiently construct a ransom note from magazine letters using Python. This guide explores 5 different implementation approaches - from basic array counting to Pythonic solutions using Counter - with detailed complexity analysis and performance tips.
Problem Definition
LeetCode Link:
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
Constraints:
1 <= ransomNote.length, magazine.length <= 105
ransomNote
andmagazine
consist of lowercase English letters.
Thought Process
At first glance, this problem may remind you of checking if one string is an anagram of another. However, the task here is slightly different: we only need to verify that magazine
provides enough characters to cover all characters required by ransomNote
. We don’t need both ways, just one direction: every character count needed by ransomNote
must be satisfied by magazine
.
Key Insight
- Since we only deal with lowercase letters, we can leverage a simple frequency array of length 26, or use dictionaries,
collections.Counter
, ordefaultdict
to store character frequencies. - Compare frequencies: if any character in
ransomNote
appears more times than it does inmagazine
, returnfalse
. - Otherwise, return
true
.
Complexity Considerations
- Time Complexity: We’ll at least need to count the characters in both strings. This is O(m + n) where m = length of
ransomNote
and n = length ofmagazine
. - Space Complexity: O(1) or O(k) where k is the character set size (26 for lowercase letters). If using dictionaries, it’s still effectively O(1) since the character set is fixed and finite.
Solution 1: Using Arrays as Frequency Counters
This approach uses two arrays of length 26—one for ransomNote
and one for magazine
—then compares frequencies.
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
ransom_count = [0] * 26
magazine_count = [0] * 26
for c in ransomNote:
ransom_count[ord(c) - ord('a')] += 1
for c in magazine:
magazine_count[ord(c) - ord('a')] += 1
# Check if magazine_count covers ransom_count for all characters
return all(ransom_count[i] <= magazine_count[i] for i in range(26))
Step-by-Step:
- Initialize two lists of length 26 to zero,
ransom_count
andmagazine_count
. - Count occurrences of each character in
ransomNote
andmagazine
. - Compare counts: for every character (from
a
toz
), ensuremagazine
has at least as many occurrences asransomNote
needs. - Return
true
if all characters are covered, otherwisefalse
.
Complexity:
- Time Complexity: O(m + n)
- Space Complexity: O(1)
Solution 2: Using collections.defaultdict
Using a defaultdict(int)
simplifies the counting logic.
from collections import defaultdict
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
char_count = defaultdict(int)
for ch in magazine:
char_count[ch] += 1
for ch in ransomNote:
if char_count[ch] <= 0:
return False
char_count[ch] -= 1
return True
Step-by-Step:
- Build a frequency dictionary for
magazine
. - For each character in
ransomNote
, decrement the count inchar_count
. - If at any point a required character’s count would drop below 0, return
false
. - If we finish without issues, return
true
.
Complexity:
- Time Complexity: O(m + n)
- Space Complexity: O(1) (since only lowercase letters)
Solution 3: Using a Dictionary with get()
Similar to the defaultdict
method, but uses a normal dictionary with get()
.
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
counts = {}
for c in magazine:
counts[c] = counts.get(c, 0) + 1
for c in ransomNote:
if counts.get(c, 0) == 0:
return False
counts[c] -= 1
return True
Step-by-Step:
- Count frequencies in
magazine
usingdict.get()
. - Iterate over
ransomNote
to ensure availability. - If shortage is found, return
false
; otherwise,true
.
Complexity:
- Time Complexity: O(m + n)
- Space Complexity: O(1)
Solution 4: Using collections.Counter
Counter
directly provides frequency counts and simplifies subtraction operations.
from collections import Counter
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
# If ransomNote requires characters that magazine doesn't have enough of, subtraction will show that.
return not (Counter(ransomNote) - Counter(magazine))
Step-by-Step:
- Create
Counter
forransomNote
andmagazine
. Counter(ransomNote) - Counter(magazine)
will remove counts fromransomNote
's counter that appear inmagazine
.- If after this subtraction there’s anything left, that means
magazine
didn’t have enough characters, so returnfalse
. - If empty, return
true
.
Complexity:
- Time Complexity: O(m + n)
- Space Complexity: O(1)
Solution 5: Using count()
Method on Strings
A more straightforward (but less efficient) Pythonic approach is to check counts character by character.
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
return all(ransomNote.count(c) <= magazine.count(c) for c in set(ransomNote))
or
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
for char in ransomNote:
if ransomNote.count(char) > magazine.count(char):
return False
return True
Step-by-Step:
- For each unique character in
ransomNote
, compare the counts inransomNote
andmagazine
. - If ever
ransomNote
needs more thanmagazine
can supply, returnfalse
. - Otherwise,
true
.
Complexity:
- Time Complexity: Potentially O(m*n) due to repeated counting operations for each unique character.
- Space Complexity: O(1)
Key Takeaways
- Frequency Counting is Key: Using arrays, dictionaries, or
Counter
is the most direct approach. - Array vs. Dictionary vs. Counter:
- Arrays are very efficient for fixed character sets (O(1) space, no hashing overhead).
Counter
is concise and clean, a good Pythonic solution.- Dictionaries and
defaultdict
offer flexible and still efficient implementations.
- Avoid Repeated
count()
Calls for Performance: While straightforward,count()
in a loop can degrade performance.
Discussion