LeetCode 383. 赎金信

在本篇博客中，我们将探讨LeetCode上的一个经典问题：383. 赎金信。这个问题考察了我们对字符串处理和字符计数的理解和应用。

问题描述

解题思路

这个问题可以通过字符计数的方法来解决。我们首先统计 magazine 中每个字符出现的次数，然后检查 ransomNote 中的每个字符是否都能在 magazine 中找到足够的数量。如果 ransomNote 中的任何一个字符在 magazine 中的数量不足，我们就返回 false。如果所有字符都能在 magazine 中找到足够的数量，我们就返回 true。

代码实现

以下是使用C++实现的代码：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // 用于记录字符出现次数的数组
        int count[26] = {0};
        // 统计magazine中每个字符出现的次数
        for (char c : magazine) {
            count[c - 'a']++;
        }
        // 检查ransomNote中的字符是否能由magazine中的字符组成
        for (char c : ransomNote) {
            if (count[c - 'a'] == 0) {
                return false;
            }
            count[c - 'a']--;
        }
        // 如果遍历完ransomNote都没有返回false，说明可以组成，返回true
        return true;
    }
};

算法分析

• 时间复杂度：O(n + m)，其中 n 是 magazine 的长度，m 是 ransomNote 的长度。我们需要遍历两个字符串来统计字符数和检查字符。

• 空间复杂度：O(1)，我们只使用了一个固定大小的数组来存储字符计数，与输入规模无关。

结论

这个问题是一个典型的字符计数问题，通过使用一个数组来记录字符的出现次数，我们可以高效地解决这个问题。这种方法不仅代码简洁，而且运行效率高，是解决类似问题的一个好方法。