LeetCode 面试经典 150_哈希表_赎金信（39_383_C++_简单）

题目描述：

给你两个字符串：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 <= 10⁵
ransomNote 和 magazine 由小写英文字母组成

题解：

解题思路：

思路一（哈希表）：

1、思路如下：

• 统计ransomNote中每种字符出现的次数，再统计magazine中每种字符出现的次数。
• 需判断ransomNote中每种出现的字符是否满足条件。
• 若ransomNote中出现的字符不存在magazine中,或者magazine中该字符出现的次数小于ransomNote中出现的次数，则可直接返回false。

2、复杂度分析：
① 时间复杂度：O(m+n)，其中 m 是字符串 ransomNote 的长度，n 是字符串 magazine 的长度，我们需要遍历两个字符串统计每种字符出现的次数，并进行比较。
② 空间复杂度：O(∣S∣)，S 是字符集，这道题中 S 为全部小写英语字母，因此 ∣S∣=26。

代码实现

代码实现（思路一（哈希表））：

class Solution
{
public:
    // 判断是否可以从 magazine 中构造 ransomNote
    bool canConstruct(string ransomNote, string magazine) {
        if(ransomNote.size()>magazine.size()){
            return false;
        }

        // 使用 unordered_map 来统计 ransomNote 中每个字符的出现次数
        unordered_map<char, int> mp_r;

        // 使用 unordered_map 来统计 magazine 中每个字符的出现次数
        unordered_map<char, int> mp_m;

        // 遍历 ransomNote，统计每个字符的频次
        for (auto const c : ransomNote) {
            mp_r[c]++;  // ransomNote 中字符 c 的出现次数加 1
        }

        // 遍历 magazine，统计每个字符的频次
        for (auto const c : magazine) {
            mp_m[c]++;  // magazine 中字符 c 的出现次数加 1
        }

        // 遍历 ransomNote 中的字符频次 map (mp_r)
        for (auto const r : mp_r) {
            // 可以通过直接访问 mp_m[r.first] 来减少 count 的调用
            // 如果没有该字符，mp_m[r.first] 默认为 0
            // 如果 magazine 中该字符的数量小于 ransomNote 中的数量，则返回 false
            if (mp_m[r.first] < r.second) {
                return false;  // magazine 中该字符的数量不足
            }
        }

        // 如果所有字符的数量都足够，返回 true，表示 ransomNote 可以从 magazine 中构造
        return true;
    }
};

以思路一为例进行调试

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution
{
public:
    // 判断是否可以从 magazine 中构造 ransomNote
    bool canConstruct(string ransomNote, string magazine) {
        if(ransomNote.size()>magazine.size()){
            return false;
        }

        // 使用 unordered_map 来统计 ransomNote 中每个字符的出现次数
        unordered_map<char, int> mp_r;

        // 使用 unordered_map 来统计 magazine 中每个字符的出现次数
        unordered_map<char, int> mp_m;

        // 遍历 ransomNote，统计每个字符的频次
        for (auto const c : ransomNote) {
            mp_r[c]++;  // ransomNote 中字符 c 的出现次数加 1
        }

        // 遍历 magazine，统计每个字符的频次
        for (auto const c : magazine) {
            mp_m[c]++;  // magazine 中字符 c 的出现次数加 1
        }

        // 遍历 ransomNote 中的字符频次 map (mp_r)
        for (auto const r : mp_r) {
            // 可以通过直接访问 mp_m[r.first] 来减少 count 的调用
            // 如果没有该字符，mp_m[r.first] 默认为 0
            // 如果 magazine 中该字符的数量小于 ransomNote 中的数量，则返回 false
            if (mp_m[r.first] < r.second) {
                return false;  // magazine 中该字符的数量不足
            }
        }

        // 如果所有字符的数量都足够，返回 true，表示 ransomNote 可以从 magazine 中构造
        return true;
    }
};

int main(int argc, char const *argv[])
{
    string ransomNote="aa";
    string magazine ="aab";
    Solution s;
    if(s.canConstruct(ransomNote,magazine)){
        cout<<"true";
    }else{
        cout<<"false";
    }
    
    return 0;
}

LeetCode 面试经典 150_哈希表_赎金信（39_383)原题链接
欢迎大家和我沟通交流(✿◠‿◠)