1 Description #
source: https://leetcode.com/problems/ransom-note/
Given two strings ransomNote and magazine, return true if ransomNote can be constructed 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 <= 10^5ransomNoteandmagazineconsist of lowercase English letters.
2 Solution #
#include <unordered_map>
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
// Time complexity: O(N + M), N is the size of ransomNode, M is the size of
// magazine Space complexity: O(26) => O(1)
// table doubling is expensive,so just preallocating the space
std::unordered_map<char, int> word_freq(26);
for (int i = 0; i < magazine.size(); i++) {
auto iter = word_freq.find(magazine[i]);
if (iter == word_freq.end()) {
word_freq[magazine[i]] = 1;
} else {
iter->second++;
}
}
for (int i = 0; i < ransomNote.size(); i++) {
auto iter = word_freq.find(ransomNote[i]);
if (iter == word_freq.end() || iter->second < 1) {
return false;
} else {
iter->second--;
}
}
return true;
}
};