383.赎金信

题目: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 = "aba"
输出：true

• 提示：

1 <= ransomNote.length, magazine.length <= 10^5
ransomNote 和 magazine 由小写英文字母组成

思路1

1. 字符计数：

   • 创建一个哈希表 map 来记录 ransomNote 中每个字符的出现次数。
   • 遍历 ransomNote 字符串，用 map.put(c, map.getOrDefault(c, 0) + 1) 来记录每个字符的频率。

2. 检查magazine中的字符：

   • 遍历 magazine 字符串，检查每个字符是否在 magazine 中出现足够次数。
   • 如果字符在 magazine 中出现，计数 -1。当字符计数等于 0 时，在哈希表中移除此字符。

3. 返回结果：

   • 当哈希表为空，代表所有字符都能满足条件，返回 true。

• 时间复杂度:O(m+n)
• 空间复杂度:O(n)

代码

public boolean canConstruct(String ransomNote, String magazine) {
    // 创建一个哈希表来记录ransomNote中每个字符出现的次数
    HashMap<Character, Integer> map = new HashMap<>();
    // 遍历ransomNote，统计每个字符的出现次数
    for (int i = 0; i < ransomNote.length(); i++) {
        char c = ransomNote.charAt(i);
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    // 遍历magazine，检查每个字符是否在magazine中出现足够次数
    for (int i = 0; i < magazine.length(); i++) {
        char c = magazine.charAt(i);
        // 如果字符在magazine中出现，计数-1。当字符计数等于0时，在哈希表中移除此字符
        if (map.computeIfPresent(c, (key, val) -> val - 1) != null && map.get(c) == 0) {
            map.remove(c);
        }
        // 当哈希表为空，代表所有字符都能满足条件，返回true
        if (map.isEmpty()) {
            return true;
        }
    }
    return false;
}

思路2

1. 字符计数：

   • 因为 ransomNote 和 magazine 由小写英文字母组成，所以可以创建一个包含26个小写字母的数组 count 来记录 magazine 中每个字符的出现次数。
   • 使用 for 循环遍历 magazine 字符串，统计每个字符的出现次数。

2. 检查ransomNote中的字符：

   • 使用 for 循环遍历 ransomNote 字符串，检查每个字符是否在 magazine 中出现足够的次数。
   • 如果某个字符不在 count 中，或者出现次数不足，则返回 false。
   • 如果某个字符可以满足需求，减少其在 count 中的计数。

3. 返回结果：

   • 如果所有字符都能满足需求，则返回 true。

• 时间复杂度:O(m+n)
• 空间复杂度:O(1)

代码

public boolean canConstruct(String ransomNote, String magazine) {
    // 创建一个数组来记录magazine中每个字符出现的次数
    int[] count = new int[26];
    // 遍历magazine，统计每个字符的出现次数
    for (int i = 0; i < magazine.length(); i++) {
        char c = magazine.charAt(i);
        count[c - 'a']++;
    }
    // 遍历ransomNote，检查每个字符是否在magazine中出现足够次数
    for (int i = 0; i < ransomNote.length(); i++) {
        char c = ransomNote.charAt(i);
        count[c - 'a']--;
        if (count[c - 'a'] < 0) {
            return false;
        }
    }
    return true;
}