LC 0383.Ransom Note

题目描述

这是 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 <= 10^5
• ransomNote 和 magazine 由小写英文字母组成

解答

方法一：计数模拟

根据题目的要求，如果 magazine 字符串的长度小于 ransomNote 字符串的长度则返回 false ，否则用数组来模拟哈希表统计 magazine 中小写字符的数目，如果 magazine 中小写字符的数目小于 ransomNote 中小写字符的数目则返回 false ，否则返回 true 。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (magazine.length() < ransomNote.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
            ++cnt[c - 'a'];
        }
        for (char c : ransomNote.toCharArray()) {
            --cnt[c - 'a'];
            if (cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

• 时间复杂度：\(O(M + N)\) ，其中 M 为 magazine 字符串的长度，N 为 ransomNote 字符串的长度。

• 空间复杂度：\(O(M + N + C)\)，如果使用 toCharArray 的话复杂度为 \(O(M + N + C)\)，其中 M 、 N 含义同上， C 为字符集的大小，如果使用 charAt 的话复杂度为 \(O(C)\) 。

每题一图