Problem Statement
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
Example
Note:
You may assume that both strings contain only lowercase letters.
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
Solution Thought Process
This is a well known hash map problem.
- Find the frequency of each element in the magazine, store them in a hash map.
- For each element in the ransom note, check the value in the map.
- If it doesn't exist, we can't make the ransom note.
- If it exists, then check if it's unused frequency is greater than 0.
- If it's greater than 0, then decrease the frequency to use it in the ransom note.
- If it's not greater than 0, then we have used up all of the characters available in the magazine, so we should return false.
Solution
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char,int>M;
bool result = true;
for(int i=0;i<magazine.size();i++)
{
if(M.find(magazine[i])==M.end())
{
M[magazine[i]]=1;
}
else {
M[magazine[i]]++;
}
}
for(int i=0;i<ransomNote.size();i++)
{
if(M.find(ransomNote[i])==M.end())
{
result = false;
break;
}
else
{
if(M[ransomNote[i]]>0)
{
M[ransomNote[i]]--;
}
else {
result = false;
break;
}
}
}
return result;
}
};
Complexity:
Time Complexity: O(m + n), where m = length of magazine and n = length of ransom note
Space Complexity: O(m) where m = length of the magazine
Top comments (0)