💵383. Ransom Note
Easy | Grind 75 | September 13rd Tuesday, 2022
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.
Constraints:
1 <= ransomNote.length, magazine.length <= 10^5ransomNoteandmagazineconsist of lowercase English letters.
Input: ransomNote = "a", magazine = "b"
Output: falseSOLUTION
We begin by building a dictionary, magazine_dict, that stores the frequency of each character that appears in the magazine variable. We then traverse through the characters in the ransomNote and check if each character exists in the magazine_dict. For the ransom note construction to be successful, we know that every character in the ransomNote must be present in the magazine_dict. While traversing through the ransom note string, when we encounter a character that is present in the magazine_dict, we decrement the count of that character in the magazine_dict by 1. This is because we can use each letter only once. If we can't construct the ransom note, we will eventually encounter a character during the traversal that is not present in the magazine_dict.
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
# magazine length need to be longer than ransomNote
if len(ransomNote) > len(magazine):
return False
# make a dictionary with letter frequency of magazine
magazine_dict = Counter(magazine)
# iterate through every ransomnote character
for char in ransomNote:
# if a ransomnote charcter is not in magazine, we know you cannot construct the note
if char not in magazine_dict:
return False
# everytime we see a charcter present, decrement the frequency count.
magazine_dict[char] -= 1
# need to remove the key if the value is 0
if magazine_dict[char] == 0:
del magazine_dict[char]
return TrueTIME AND SPACE COMPLEXITY
TIME: O(n) where n is the length of the magazine string. We build the magazine string into a dictionary which has a runtime of O(n). Also, given that you can only use each character once, you need to have the length of the magazine string either longer or equal to the lenght of ransomNote.
SPACE: O(n) where n is the length of the magazine string. We build the magazine_dict which in the worst case will take up n space.
Last updated