LeetCode 383、赎金信（HJ81. 字符串字符匹配）

一、题目描述

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

二、题目解析

三、参考代码

方法一

哈希集合遍历解法

# 题目：LC383. 赎金信
# 难度：简单
# 作者：闭着眼睛学数理化
# 算法：哈希集合遍历解法
# 代码看不懂的地方，请直接在群上提问

# 导入collections中的Counter计数器类，使用dict()也可以但是代码就要多一些判断
from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # 用两个哈希表保存R和M两个字符串中所有元素出现的频率
        cnt_R, cnt_M = Counter(ransomNote),  Counter(magazine)
        
        # 由于要计算R是否能够被M完全包含，所以我们要遍历R中的字符
        # 遍历cnt_R中的所有字符
        for ch in cnt_R:
            # 如果发现ch在R中的数目大于在M中的数目，则返回False
            if cnt_R[ch] > cnt_M[ch]:
                return False
        
        # 成功退出循环，返回True
        return True

方法二

用列表表示哈希表进行统计

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 赎金信（LeetCode 383）：https://leetcode.cn/problems/ransom-note/
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {

        // 手动设置哈希表
        // 这里的哈希表的作用是计数器
        // 由于小写字母的个数为 26 个，所以数组大小为 26
        int[] cnt = new int[26];


        // 记录 magazine 里字母出现的次数
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }
        
        // 再用 ransomNote 去验证这个数组是否包含了 ransomNote 所需要的所有字母
        for (char c : ransomNote.toCharArray()) {
            // 在遍历过程中，每遍历一个字母，对应的频次减 1
            cnt[c - 'a']--;

            // 如果发现某个字母的频次小于了 0
            // 说明在 ransomNote 中出现了 magazine 未曾有的字母
            // 即 ransomNote 不能由 magazine 里面的字符构成
            if(cnt[c - 'a'] < 0) {

                // 返回 false 
                return false;
            }
        }

        // 说明可以，返回 true 
        return true;
    }
}

**2、**C++ 代码

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {

        // 手动设置哈希表
        // 这里的哈希表的作用是计数器
        // 由于小写字母的个数为 26 个，所以数组大小为 26
        vector<int> cnt(26);


        // 记录 magazine 里字母出现的次数
        for (auto & c : magazine) {
            cnt[c - 'a']++;
        }
        
        // 再用 ransomNote 去验证这个数组是否包含了 ransomNote 所需要的所有字母
        for (auto & c : ransomNote) {
            // 在遍历过程中，每遍历一个字母，对应的频次减 1
            cnt[c - 'a']--;

            // 如果发现某个字母的频次小于了 0
            // 说明在 ransomNote 中出现了 magazine 未曾有的字母
            // 即 ransomNote 不能由 magazine 里面的字符构成
            if(cnt[c - 'a'] < 0) {

                // 返回 false 
                return false;
            }
        }

        // 说明可以，返回 true 
        return true;

    }
};

3、Python 代码

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # 手动设置哈希表
        # 这里的哈希表的作用是计数器
        # 由于小写字母的个数为 26 个，所以数组大小为 26
        cnt = [0] * 26

        # 记录 magazine 里字母出现的次数
        for ch in magazine:  
            # 对于数组类型，其下标为 int 类型
            # 可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码
            # 比如 ch 是 b 字符，那么 b - a = 1，即 needs[1] 表示记录 b 出现的频次 
            idx = ord(ch) - ord('a')
            cnt[idx] += 1
        

        # 再用 ransomNote 去验证这个数组是否包含了 ransomNote 所需要的所有字母
        for ch in ransomNote:  
            # 在遍历过程中，每遍历一个字母，对应的频次减 1
            cnt[ord(ch) - ord('a')] -= 1

            # 如果发现某个字母的频次小于了 0
            # 说明在 ransomNote 中出现了 magazine 未曾有的字母
            # 即 ransomNote 不能由 magazine 里面的字符构成
            if cnt[ord(ch) - ord('a')] < 0 :

               return False

        # 说明可以，返回 true 
        return True