摘要

这道题其实是一个很“生活化”的问题：给定两段文字，判断第一段文字（赎金信）能不能完全用第二段文字（杂志）里的字母拼出来。换句话说，你能不能从杂志里“剪字母”，凑成一封赎金信。

在程序实现上，本质就是统计字符的数量，看 magazine 里的字母是否够 ransomNote 用。本文会一步步带你分析题目，给出 Swift 的可运行 Demo，并结合一些生活场景来帮助理解。

描述

题目要求：

• 给定两个字符串：ransomNote 和 magazine。
• 判断 ransomNote 是否可以由 magazine 里的字母构成。
• 每个字母在 magazine 里只能使用一次。

示例：

输入: ransomNote = "a", magazine = "b"
输出: false

输入: ransomNote = "aa", magazine = "ab"
输出: false

输入: ransomNote = "aa", magazine = "aab"
输出: true

直观来说，如果你要写一封信，手里只有一本杂志，你得剪出字母去拼，杂志上的字母数量必须足够，不然拼不出来。

题解答案

解题的关键点就是 字符频率统计。思路很简单：

1. 遍历 magazine，统计每个字母出现的次数。

2. 再遍历 ransomNote，看看里面的字母在 magazine 统计里是不是足够。

   • 如果某个字母不够用，直接返回 false。
   • 如果全部字母够用，就返回 true。

这就是一个典型的 哈希表计数 问题。因为题目限定了字母范围是 a-z，所以我们可以用数组来代替哈希表，提升效率。

题解代码分析

下面是 Swift 实现：

import Foundation

class Solution {
    func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
        // 用一个长度为26的数组来统计 magazine 中字母的出现次数
        var count = Array(repeating: 0, count: 26)
        
        // 遍历 magazine，统计每个字符数量
        for char in magazine {
            let index = Int(char.asciiValue! - Character("a").asciiValue!)
            count[index] += 1
        }
        
        // 遍历 ransomNote，检查 magazine 是否有足够的字符
        for char in ransomNote {
            let index = Int(char.asciiValue! - Character("a").asciiValue!)
            count[index] -= 1
            if count[index] < 0 {
                return false
            }
        }
        
        return true
    }
}

代码拆解

1. 统计 magazine

   • 用数组 count[26] 统计每个字母的数量，索引通过 asciiValue 计算得出。
   • 例如，字符 'a' 的索引是 0，字符 'c' 的索引是 2。

2. 验证 ransomNote

   • 遍历 ransomNote 的每个字母，每次遇到一个字母，就把对应计数减一。
   • 如果某个字母数量小于 0，就说明 magazine 里的字母不够用，返回 false。

3. 全部检查完毕

   • 如果过程中没有失败，说明 magazine 足够覆盖 ransomNote，返回 true。

示例测试及结果

我们来写几个测试用例：

let solution = Solution()

print(solution.canConstruct("a", "b"))      // false
print(solution.canConstruct("aa", "ab"))    // false
print(solution.canConstruct("aa", "aab"))   // true

运行结果：

false
false
true

这正好对应题目给出的示例，说明实现是正确的。

时间复杂度

• 遍历 magazine：O(m)
• 遍历 ransomNote：O(n)
• 总复杂度：O(m + n)，其中 m 和 n 分别是两个字符串的长度。

空间复杂度

• 使用了一个固定长度的数组 count[26]，无论字符串多大，空间占用都是 O(1)。

总结

这道题看似是个简单的字符串处理问题，但其实体现了一个很常见的思路：频率统计。

在实际工作中，类似的需求也很常见：

• 判断一篇文章是否包含另一篇文章的所有关键词。
• 判断一个用户请求是否在某个资源池里能被完全满足。
• 或者在游戏里，玩家背包里的材料是否足够合成某个装备。

所以，虽然 LeetCode 383 题目叫“赎金信”，但本质上是 资源是否足够的验证问题。学会了这种思路，在很多场景下都能用得上。