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

提示：

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

解题方法：

解法一：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char,int> ransom;
        unordered_map<char,int> magaz;
        for(auto ch:ransomNote)
        {
            ransom[ch]++;
        }
        for(auto ch:magazine)
        {
            magaz[ch]++;
        }
        for(auto note:ransom)
        {
            if(magaz[note.first]<note.second)   //只要magazine中字符大于等于ransom中字符就行
                return false;
        }
        return true;
    }
};

解法二：

// 时间复杂度: O(n)
// 空间复杂度：O(1)
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        for (int i = 0; i < magazine.length(); i++) {
            // 通过recode数据记录 magazine里各个字符出现次数
            record[magazine[i]-'a'] ++; 
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            // 遍历ransomNote，在record里对应的字符个数做--操作
            record[ransomNote[j]-'a']--; 
            // 如果小于零说明 magazine里出现的字符，ransomNote没有
            if(record[ransomNote[j]-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

做题小结：

针对解法一：

1. 思路很简单，但是空间复杂度较高，所花时间也比较多

针对解法二：

1. 对于这种处理字母数量的题，在使用哈希表时，最好就用一个26空间的int数组来进行，数组所花的空间比map要小很多