383. 赎金信

题目描述

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

你可以假设两个字符串均只含有小写字母。

题解

思路：本题使用数组的哈希法做过(因为两个字符串中只有小写字母)；此处我们采用unordered_map来做：先分别统计两个字符串中的字符(字符做key，个数做value)，然后再将两个map进行对比即可。

代码(C++)：

unordered_map<char, int> sCount(string s) {
    unordered_map<char, int> map;
    for (int i = 0; i < s.size(); i++) {
        auto iter = map.find(s[i]);
        if (iter != map.end()) {
            iter->second++;
        }else {
            map.insert(pair<char, int>(s[i],1));
        }
    }
    return map;
}

bool canConstruct(string ransomNote, string magazine) {
    unordered_map<char, int> map1 = sCount(ransomNote);
    unordered_map<char, int> map2 = sCount(magazine);
    for (auto iter1 : map1) {
        auto iter2 = map2.find(iter1.first);
        if (iter2 == map2.end() || iter2->second < iter1.second){
            return false;
        }
    }
    return true;
}

分析：在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。所以数组更加简单直接有效！（来自：代码随想录）