50 lines
962 B
C++
50 lines
962 B
C++
#include <cassert>
|
|
#include <map>
|
|
#include <string>
|
|
|
|
namespace {
|
|
|
|
std::map<char, int> build_freqs(const std::string &input) {
|
|
std::map<char, int> freqs;
|
|
|
|
for (auto c : input) {
|
|
freqs[c]++;
|
|
}
|
|
|
|
return freqs;
|
|
}
|
|
|
|
bool subtract(std::map<char, int> available, const std::string &message) {
|
|
for (auto c : message) {
|
|
available[c]--;
|
|
|
|
if (available[c] < 0) {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
} // namespace
|
|
|
|
class Solution {
|
|
public:
|
|
bool canConstruct(const std::string &ransomNote,
|
|
const std::string &magazine) {
|
|
auto available = build_freqs(magazine);
|
|
return subtract(available, ransomNote);
|
|
}
|
|
};
|
|
|
|
int main() {
|
|
Solution s;
|
|
|
|
assert(!s.canConstruct("a", "b"));
|
|
assert(!s.canConstruct("aa", "ab"));
|
|
assert(s.canConstruct("aa", "aab"));
|
|
assert(s.canConstruct("ab", "aab"));
|
|
assert(s.canConstruct("ba", "aab"));
|
|
|
|
return 0;
|
|
}
|