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 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ransom-note

方法一：字符统计

题目要求使用字符串 magazine 中的字符来构建新的字符串 ransomNote，且ransomNote 中的每个字符只能使用一次，只需要满足字符串 magazine中的每个英文字母 (’a’-’z’)的统计次数都大于等于ransomNote 中相同字母的统计次数即可。

如果字符串 magazine 的长度小于字符串 ransomNote 的长度，则我们可以肯定 magazine 无法构成 ransomNote，此时直接返回 false。

首先统计 magazine 中每个英文字母 a 的次数 cnt[a]，再遍历统计 ransomNote 中每个英文字母的次数，如果发现
ransomNote 中存在某个英文字母c的统计次数大于 magazine 中该字母统计次数cnt[c]，则此时我们直接返回 false。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/ransom-note/solution/shu-jin-xin-by-leetcode-solution-ji8a/
来源：力扣（LeetCode）

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // 如果ransomNote的长度大于magazine的长度，显然无法构造
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        // 定义一个大小为26的计数数组cnt，记录magazine中每个字符出现的次数
        vector<int> cnt(26);
        for (auto & c : magazine) {
            cnt[c - 'a']++;
        }
        // 遍历ransomNote中的每个字符，如果cnt中对应字符的计数器小于0，则无法构造
        for (auto & c : ransomNote) {
            cnt[c - 'a']--;
            if (cnt[c - 'a'] < 0) {
                return false;
            }
        }
        // 如果ransomNote中的每个字符在magazine中都能找到，则可以构造
        return true;
    }
};

解释

        vector<int> cnt(26);
        for (auto & c : magazine) {
            cnt[c - 'a']++;
        }

这段代码是用来遍历字符串 magazine，并统计每个字符出现的次数。

使用了一个循环语句和一个计数数组 cnt，循环遍历字符串 magazine 中的每个字符 c。对于每个字符 c，通过 c - 'a' 的运算来将字符转化为对应的下标，然后将计数数组 cnt 中对应下标的元素值加一，表示字符 c 出现了一次。

其中，'a' 表示 ASCII 码表中小写字母表中的第一个字母，将字符 c 减去 'a' 后得到的结果就是其在字母表中的位置，因此可以用来作为计数数组的下标。

这段代码的作用是为后面判断字符串 ransomNote 是否能够由 magazine 中的字符组成做准备，通过统计 magazine 中每个字符出现的次数，可以方便地判断 ransomNote 中每个字符在 magazine 中是否有足够的数量来组成。

假设 magazine 为 "aabbcdd"，则在遍历字符串 magazine 的过程中，计数数组 cnt 会被修改为：

cnt[0] = 2  // 'a' 出现了两次
cnt[1] = 2  // 'b' 出现了两次
cnt[2] = 0  // 'c' 没有出现
cnt[3] = 2  // 'd' 出现了两次
cnt[4] = 0  // 'e' 没有出现
...

其中，数组下标从 0 开始，因此 cnt[0] 表示小写字母表中的第一个字母 'a' 出现的次数，cnt[1] 表示小写字母表中的第二个字母 'b' 出现的次数，以此类推。

 cnt[c - 'a']++;  

假设当前遍历到的字符 c 是小写字母 'b'，则可以将其转化为数组下标 c - 'a'，即 'b' - 'a' = 1，于是执行语句 cnt[c - 'a']++ 就相当于 cnt[1]++，即将计数数组 cnt 中下标为 1 的元素值加一。

在遍历字符串 magazine 的过程中，如果有多个字符 'b'，则会多次执行 cnt[c - 'a']++ 这句代码，每次都会将计数数组中下标为 1 的元素值加一。最终，数组 cnt 中下标为 1 的元素值就会等于字符 'b' 在字符串 magazine 中出现的次数。

        // 遍历ransomNote中的每个字符，如果cnt中对应字符的计数器小于0，则无法构造
        for (auto & c : ransomNote) {
            cnt[c - 'a']--;
            if (cnt[c - 'a'] < 0) {
                return false;
            }
        }

这段代码是用来遍历字符串 ransomNote 中的每个字符，并判断是否能够由字符串 magazine 中的字符组成。

首先，使用一个循环语句遍历字符串 ransomNote 中的每个字符 c，并将计数数组 cnt 中对应字符的计数器减一，表示使用了一个该字符。这里同样使用了 c - 'a' 的运算来将字符转化为对应的下标，然后将计数数组 cnt 中对应下标的元素值减一。

然后，判断计数数组 cnt 中对应字符的计数器是否小于 0，如果是则说明字符串 magazine 中没有足够的该字符来组成 ransomNote，直接返回 false。

最后，如果遍历 ransomNote 中的每个字符都没有返回 false，则说明 ransomNote 可以由 magazine 中的字符组成，返回 true。

这段代码的作用是判断字符串 ransomNote 是否能够由字符串 magazine 中的字符组成。在之前的遍历 magazine 的过程中，计数数组 cnt 统计了 magazine 中每个字符出现的次数。现在遍历 ransomNote 中的每个字符，并将计数数组中对应字符的计数器减一，如果在遍历 ransomNote 的过程中发现某个字符在 magazine 中出现的次数不够，即计数器小于 0，说明无法由 magazine 中的字符组成 ransomNote，直接返回 false。

二

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
    // 定义一个大小为26的数组hash，用来记录magazine中每个字符出现的次数
    std::array<int, 26> hash = {0};
    // 使用 C++ 11 的范围 for 循环可以使代码更加简洁明了
    for (auto c : magazine) {
        // 遍历magazine中的每个字符，将对应字符的计数器加1
        hash[c - 'a']++;
    }
    for (auto c : ransomNote) {
        // 遍历ransomNote中的每个字符，将对应字符的计数器减1
        hash[c - 'a']--;
        // 如果hash中对应字符的计数器小于0，则无法构造
        if (hash[c - 'a'] < 0) {
            return false;
        }
    }
    // 如果ransomNote中的每个字符在magazine中都能找到，则可以构造
    return true;
 }
};

std::array<int, 26> hash 和 vector<int> cnt(26) 都是用来创建大小为 26 的数组的，但它们之间有一些区别。

1. 固定大小 vs 可变大小：std::array 是一个固定大小的数组，大小在编译时就已经确定，不能改变。而 vector 是一个动态数组，大小可以在运行时动态调整。
2. 空间占用：由于 std::array 的大小是固定的，在创建数组时就已经分配了固定大小的内存，因此在空间占用方面比 vector 更加高效。而 vector 需要在运行时动态分配内存，可能会导致空间浪费。
3. 访问元素：std::array 和 vector 都支持使用下标访问元素，但 std::array 的访问速度更快。这是因为 std::array 的元素是存储在连续的内存空间中的，而 vector 的元素是可能被分散存储在不同的内存块中的。

综上所述，当需要创建大小固定的数组时，建议使用 std::array，因为它在空间占用和访问速度方面都更加高效。而当需要动态调整数组大小时，建议使用 vector。