Ransom Note
- 1 min read
- String
- LC-Easy
3 years ago
Solution
- We can use two hashmaps or array where key is character and value is occurence
- Loop through each unique character in ransom note, and check if frequency in magazine note is lesser than frequency in ransom note. If so, return False. If end of code is reached, return True.
- This solution uses two hashmaps. And although space complexity is contact due to limited character set, we can solve this problem using a single hash map.
- Make hashmap of magazine. Loop through ransom note, decrementing character count. If character count is 0 before we decrement, it means we ran out of characters in the magazine to construct the ransom note, so return False
- If end of loop is reached, return True.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) | Limited charset, so space complexity is constant. |
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
mag_count = Counter(magazine)
for ch in ransomNote:
if ch not in mag_count or mag_count[ch] == 0:
return False
mag_count[ch] -= 1
return True