题解 | 字符串构造判定

使用c++ hashmap实现(无序unordered_map)：

读取T中的所有字符，对字符value加一。

读取S中所有字符，对map中的对应字符减一。

最后遍历一遍map，如果发现了有任意一个value小于0，说明S的字符数量超过T中字符了，返回false。

否则返回true。

#include <unordered_map>
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> m;
        for(char i:magazine) m[i]++;
        for(char i:ransomNote) m[i]--;
        for(auto [i,j]:m){
            if(j<0) return false;
        }
        return true;
    }
};

解法二、使用c++ multiset：

读取T中的所有字符，插入字符。

读取S中所有字符，对于每一次，如果找到该字符，将其删除。

如果找不到字符，说明无法从T中构造出S。

#include <set>
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        multiset<char> m;
        for(char i:magazine) m.insert(i);
        for(char i:ransomNote){
            auto it = m.find(i);
            if (it == m.end()) {
                return false;
            }
            m.erase(it);
        }
        return true;
    }
};