LeetCode: Ransom Note

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