Description
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.
Note: You may assume that both strings contain only lowercase letters.
给定一个任意的表示勒索信内容的字符串，和另一个字符串表示杂志的内容，写一个方法判断能否通过剪下杂志中的内容来构造出这封勒索信，若可以，返回 true；否则返回 false。
杂志字符串中的每一个字符仅能在勒索信中使用一次。
Examples
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
Answer
Since magazines and notes only contains lowercase letters, we can store the number of each characters in magazine in a vector or an array, then check if characters covered in magazine are enough to composite the note.
Time Complexity
O(n + m) which n refers to length of magazine and m refers to length of note.
Code
C++
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if(magazine.size() < ransomNote.size()) return false;
int count[26] = {0};
for(auto c : magazine)
count[c - 'a']++;
for(auto c : ransomNote)
{
if(count[c - 'a']-- <= 0)
return false;
}
return true;
}
};
