Ransom Note

383. 赎金信

分析

构建字符频率表
- 遍历 magazine，统计每个字符出现的次数。
逐字符匹配
- 如果 hash[c] > 0，说明字符可用，使用后数量减 1
- 如果 hash[c] == 0，说明字符不足，返回 false
全部匹配成功
- 如果遍历完 ransomNote 没有提前返回 false，则说明可以成功构造，返回 true

时间复杂度

时间复杂度 O(n + m)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution
{
public:
    bool canConstruct(string ransomNote, string magazine)
    {
        // 1. 统计 magazine 中字符的频率
        std::unordered_map<char, int> hash;
        for (char c : magazine)
            ++ hash[c];  // 每个字符的出现次数

        // 2. 遍历 ransomNote，检查字符是否足够
        for (char c : ransomNote)
        {
            if (hash[c] > 0)
                --hash[c];  // 使用一个字符，数量减少
            else
                return false;  // 不足时，直接返回 false
        }

        // 3. 所有字符都有足够数量，返回 true
        return true;
    }
};