The original problem of “383. Ransom Note” was published on LeetCode.com
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 <= 105ransomNoteandmagazineconsist of lowercase English letters.
Understanding the problem
Solution code is required that accepts two strings, ‘ransomNote’ and ‘magazine’, and returns true if the ‘ransomNote’ can be constructed from the letters in ‘magazine’. This time, each letter from ‘magazine’ can be used only once in ‘ransomNote’, and both strings can be comprised of upper and lowercase English letters. Examples and corresponding expected outputs are provided above.
How to solve this problem?
You will need to understand how to parse a string and create a data structure to store the individual letters of the string. You could use a hashmap/dictionary, an array, or perhaps a set, which stores the individual letters. You will also need to understand how to loop over the strings, compare letters from each string to each other, count instances of each letter, and then compare the number of instances of each letter in each string. Once the comparison is made, you can decide if the ‘ransomNote’ can be constructed from the letters in ‘magazine’ or not.
How to parse a string and create a data structure to store the individual letters of it?
You will need to create a data structure to store the individual letters of a string. Then to loop over the strings, compare letters from each string to each other, and count instances of each letter. After that compare the number of instances of each letter in each string, you could use a loop and a dictionary to store the count of each letter. For example, if we have the strings “This is a sample string” and “Example string”:
string1 = "This is a sample string"
string2 = "Example string"
# Store letter counts in dictionary
letter_count_dict = {}
# Loop over string 1
for letter in string1:
# Check if letter is already in the dictionary
if letter in letter_count_dict:
# If so, increment value
letter_count_dict[letter] += 1
elif letter == ' ':
# Ignore spaces
continue
else:
# If not, add letter to dictionary with value of 1
letter_count_dict[letter] = 1
# Loop over string 2
for letter in string2:
# Check if letter is already in the dictionary
if letter in letter_count_dict:
# If so, increment value
letter_count_dict[letter] += 1
elif letter == ' ':
# Ignore spaces
continue
else:
# If not, add letter to dictionary with value of 1
letter_count_dict[letter] = 1
# Print out the dictionary containing letter counts
print(letter_count_dict) # Output: {'T': 1, 'h': 1, 'i': 2, 's': 4, 'a': 1, 'm': 1, 'p': 1, 'l': 1, 'e': 3, 'g': 1, 't': 1}Once the dictionary is complete, you can compare the counts of each letter in both strings and decide if the ‘ransomNote’ can be constructed from the letters in ‘magazine’.
This code takes two strings, “This is a sample string” and “Example string”, and stores their letter counts in a dictionary. It does this by looping over each string, checking if each letter is already in the dictionary and, if so, incrementing its value, or if the letter is not yet present, adding it to the dictionary with a value of 1. Finally, the code prints out the dictionary containing all of the letter counts.
Let’s develop the solution
We can use a hashmap/dictionary to store each of the characters in both strings and their counts. We will keep track of which characters are already in the dictionary, and increment their values if they already exist, or add them if they do not. We will also need to compare the resulting dictionary of letter counts against the letter count of ‘magazine’, and decide if the ‘ransomNote’ can be constructed from the letters in ‘magazine’.
# Function to decide if ransomNote can be constructed using magazine
def canConstruct(ransomNote, magazine):
# Create dictionary to store letter counts
letter_count_dict = {}
# Loop over magazine
for letter in magazine:
# Check if letter is already in the dictionary
if letter in letter_count_dict:
# If so, increment value
letter_count_dict[letter] += 1
elif letter == ' ':
# Ignore spaces
continue
else:
# If not, add letter to dictionary with value of 1
letter_count_dict[letter] = 1
# Loop over ransomNote
for character in ransomNote:
# Check if character is already in the dictionary
# and if there are enough instances of the character
if character in letter_count_dict and letter_count_dict[character] > 0:
# Decrement value
letter_count_dict[character] -= 1
else:
# If not, return False
return False
# If all characters in ransomNote have been found, return True
return True This code checks if the ‘ransomNote’ can be constructed using letters from the ‘magazine’. It first creates a dictionary to store the letter counts of both strings. It then loops over ‘magazine’ and adds each letter to the dictionary, incrementing its count if it already exists, or adding it with a value of 1 if not.
It then loops over ‘ransomNote’, checking if the character is present in the dictionary and if there are enough instances of that character. If the character is present and there are enough instances, it decrements the count in the dictionary. If the character is not present or there are not enough instances, it returns False. If all of the characters in ‘ransomNote’ have been found, it returns True.
What is the time complexity of this code?
The time complexity of this code is O(N) where N is the sum of the lengths of the two strings ‘ransomNote’ and ‘magazine’. This is because the code loops over both strings at most once, so the runtime complexity is linear with respect to the length of the input.
What is the space complexity of this code?
The space complexity of this code is O(M) where M is the length of the ‘magazine’ string. This is because the code creates a dictionary that stores the letter counts of ‘magazine’, requiring linear space with the length of ‘magazine’.
