【LeetCode】383. 赎金信

题目描述

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = “a”, magazine = “b”
输出：false
示例 2：
输入：ransomNote = “aa”, magazine = “ab”
输出：false
示例 3：
输入：ransomNote = “aa”, magazine = “aab”
输出：true
提示：
1 <= ransomNote.length, magazine.length <= 105
ransomNote 和 magazine 由小写英文字母组成

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // 记录magazine里各个字符出现次数
        int magazineArray[26] = {0};
        for(int i=0; i < magazine.length(); i++){
            magazineArray[magazine[i]-'a']++;
        }
        for(int j=0; j < ransomNote.length(); j++){
            magazineArray[ransomNote[j]-'a']--;
            //一旦小于0则说明后者无法构成前者；
            if(magazineArray[ransomNote[j]-'a'] < 0)
                return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

心得：
本科的时候很害怕字符串相关的题目，对于这方面还是得多加练习。
1.一开始想走捷径，查找字符串的相关函数，发现了s.find()子串函数，但后来发现这个思路不对，因为只要magazine里的字符能够组成ransomNote即可，也就是magazine的字符个数要>=ransomNote。
2.之后，想要通过暴力求解的方法完成这道题，试图遍历ransomNote和magazine的字符并计数，之后两者相比，如果前者大于后者则说明false，但这种方法时间复杂度过高。
3.通过浏览评论区发现，可以考虑空间换时间的哈希表，也就是本文最后使用的方法，遍历magazine的字符并计数，之后再次遍历ransomNote字符做递减，一旦magazineArray<0说明匹配失败。