0383. Ransom Note

题目信息

题号:

0383

难度:

Easy

主题:

两个字符串、字符频次、一次性使用、小写字母

原题:

LeetCode 0383

重点:

杂志中的每个字符实例最多使用一次、字符顺序无关、每种字母数量必须足够

题目重述

给定字符串 ransomNote 和 magazine,判断能否从 magazine 提供的字符中取出若干字符,重新排列后组成完整的 ransomNote。magazine 中的每个字符位置最多使用一次。

两个字符串长度均位于 [1, 10^5],只包含小写英文字母。若 ransomNote 中任意字母所需次数超过它在 magazine 中的出现次数,应返回 false;多余的杂志字符可以不使用。

自建示例

杂志字符足够:

输入:ransomNote = "note",magazine = "stone"
输出:true
解释:magazine 中各有一个 n、o、t、e,可以重新排列组成 note,多余的 s 不必使用。

重复字母不足:

输入:ransomNote = "aabc",magazine = "abc"
输出:false
解释:目标需要两个 a,而 magazine 中只有一个 a,同一个字符位置不能使用两次。

比较 26 种字符的剩余额度

先把 magazine 中每个字母的可用次数记入数组,再扫描 ransomNote,每取出一个字母就消耗一个额度;任一额度变成负数,说明杂志中的字符实例不够。字符顺序无关,所以不需要模拟具体取出位置。

C++ 实现

class Solution {
public:
    bool canConstruct(std::string ransomNote,
                      std::string magazine) {
        std::array<int, 26> remaining{};
        for (char c : magazine) ++remaining[c - 'a'];
        for (char c : ransomNote) {
            if (--remaining[c - 'a'] < 0) return false;
        }
        return true;
    }
};

代码分析

每个目标字符都对应一次额度消耗,因而恰好表达“同一字符位置不能重复使用”;多余的 magazine 字符不影响结果。时间复杂度为 O(ransomNote.size() + magazine.size()),额外空间为固定的 O(1)。