383_赎金信

【问题描述】

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。

示例一：
输入：ransomNote = "a", magazine = "b"
输出：false

示例二：
输入：ransomNote = "aa", magazine = "ab"
输出：false

示例三：
输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote 和 magazine 由小写英文字母组成

【算法设计思想】

字符频率统计：

使用一个固定大小的数据结构（如数组、哈希表等）来统计magazine中每个字符的出现频率。由于题目限定了只包含小写英文字母，所以可以使用一个长度为26的整型数组来存储每个字母的出现次数。

频率对比：

遍历ransomNote中的每个字符，检查这些字符在之前创建的频率统计表中是否有足够的数量。如果对于ransomNote中的任意一个字符，其在magazine中的出现次数少于所需，则不能构建该ransomNote，返回false。
如果所有字符都能满足条件，则可以构建ransomNote，返回true。

【算法描述】

C++：

class Solution {
public:
    // 检查能否使用 magazine 中的字符构造 ransomNote
    bool canConstruct(string ransomNote, string magazine) {
        // 如果 ransomNote 的长度大于 magazine，则无法构造
        if (ransomNote.size() > magazine.size()) {
            return false;
        }

        // 使用数组记录 magazine 中字符的出现次数（假设只包含小写字母）
        int map[26] = {0};

        // 遍历 magazine 中的每个字符，并记录每个字符的出现次数
        for (int i = 0; i < magazine.size(); i++) {
            map[magazine[i] - 'a']++;
        }

        // 遍历 ransomNote 中的每个字符，减少 map 中对应字符的计数
        for (int i = 0; i < ransomNote.size(); i++) {
            map[ransomNote[i] - 'a']--;
            // 如果计数小于 0，说明字符不够用，无法构造 ransomNote
            if (map[ransomNote[i] - 'a'] < 0) {
                return false;
            }
        }

        // 如果所有字符都能匹配，返回 true
        return true;
    }
};

Java：

class Solution {
    // 方法：检查是否可以使用 magazine 中的字符构造 ransomNote
    public boolean canConstruct(String ransomNote, String magazine) {
        // 定义一个数组来记录 magazine 中每个字符的出现次数（假设只有小写字母）
        int[] map = new int[26];

        // 遍历 magazine 中的每个字符，并记录每个字符的出现次数
        for (int i = 0; i < magazine.length(); i++) {
            map[magazine.charAt(i) - 'a']++;
        }

        // 遍历 ransomNote 中的每个字符，减少 map 中对应字符的计数
        for (int i = 0; i < ransomNote.length(); i++) {
            map[ransomNote.charAt(i) - 'a']--;
            // 如果计数小于 0，说明 magazine 中的字符不够用，无法构造 ransomNote
            if (map[ransomNote.charAt(i) - 'a'] < 0) {
                return false;
            }
        }

        // 如果所有字符都能匹配，则返回 true
        return true;
    }
}

Python：

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # 初始化一个长度为26的列表，用于存储magazine中每个字母的数量
        letter_count = [0] * 26
        
        # 遍历magazine中的每个字符，并增加对应位置的计数
        for char in magazine:
            letter_count[ord(char) - ord('a')] += 1
        
        # 遍历ransomNote中的每个字符，减少letter_count中对应位置的计数
        for char in ransomNote:
            letter_count[ord(char) - ord('a')] -= 1
            # 如果某个字符的数量小于0，说明magazine中该字符的数量不足以构成ransomNote
            if letter_count[ord(char) - ord('a')] < 0:
                return False
        
        # 如果所有字符的数量都足够，则返回True
        return True

C：

// 判断是否可以从magazine字符串中构建出ransomNote字符串
bool canConstruct(char* ransomNote, char* magazine) {
    // 创建一个大小为26的数组来记录每个小写字母在magazine中的出现次数
    int map[26] = {0};

    // 遍历magazine字符串，统计每个字符出现的次数
    for (int i = 0; i < strlen(magazine); i++) {
        // 将字符转换为数组索引（'a'->0, 'b'->1, ..., 'z'->25）并递增对应的计数
        map[magazine[i] - 'a']++;
    }

    // 遍历ransomNote字符串，检查所需的字符数量是否不超过magazine中的可用数量
    for (int i = 0; i < strlen(ransomNote); i++) {
        // 对于ransomNote中的每个字符，减少其在map中的计数
        map[ransomNote[i] - 'a']--;

        // 如果某个字符的计数变为负数，说明magazine中的该字符不足以构建ransomNote
        if (map[ransomNote[i] - 'a'] < 0) {
            return false; // 返回false表示无法构建
        }
    }

    // 如果成功遍历完ransomNote且没有计数变为负数，说明可以构建
    return true;
}