LeetCode 383 赎金信

摘要

这道题其实挺有意思的，它模拟了一个经典的场景：用杂志上的字母拼出勒索信。题目要求我们判断ransomNote能不能由magazine里面的字符构成，而且magazine中的每个字符只能用一次。

听起来像是一个字符串匹配问题，但实际上是一个字符计数问题。我们需要统计magazine中每个字符的出现次数，然后检查ransomNote中的每个字符是否都有足够的数量。今天我们就用 Swift 来搞定这道题，顺便聊聊这种字符计数的方法在实际开发中的应用场景。

描述

题目要求是这样的：给你两个字符串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，每遇到一个字符，就从统计中减去一次。如果某个字符的计数变成负数，说明magazine中没有足够的字符来构成ransomNote，返回false。如果遍历完ransomNote都没有出现负数，说明可以构成，返回true。

题解答案

下面是完整的 Swift 解决方案：

classSolution{funccanConstruct(_ransomNote:String,_magazine:String)->Bool{// 统计 magazine 中每个字符的出现次数varcharCount:[Character:Int]=[:]forcharinmagazine{charCount[char,default:0]+=1}// 遍历 ransomNote，检查每个字符是否都有足够的数量forcharinransomNote{// 如果字符不存在或数量不足，返回 falseifletcount=charCount[char],count>0{charCount[char]=count-1}else{returnfalse}}returntrue}}

题解代码分析

让我们一步步分析这个解决方案：

1. 字符计数的方法

这道题的核心是统计字符的出现次数。我们可以用一个字典来存储每个字符及其出现次数：

varcharCount:[Character:Int]=[:]

字典的键是字符，值是该字符在magazine中出现的次数。

2. 统计 magazine 中的字符

首先，我们需要统计magazine中每个字符的出现次数：

forcharinmagazine{charCount[char,default:0]+=1}

这里使用了 Swift 字典的default参数，如果字符不存在，默认值为 0，然后加 1。如果字符已存在，就直接加 1。

示例：

假设magazine = "aab"：

• 遍历到 ‘a’：charCount['a'] = 1
• 遍历到 ‘a’：charCount['a'] = 2
• 遍历到 ‘b’：charCount['b'] = 1

最终charCount = ['a': 2, 'b': 1]

3. 检查 ransomNote 中的字符

接下来，我们需要检查ransomNote中的每个字符是否都有足够的数量：

forcharinransomNote{ifletcount=charCount[char],count>0{charCount[char]=count-1}else{returnfalse}}

对于ransomNote中的每个字符：

1. 检查该字符是否在字典中存在，且数量大于 0
2. 如果存在且数量足够，将该字符的计数减 1
3. 如果不存在或数量不足，返回false

示例：

假设ransomNote = "aa"，magazine = "aab"：

• 第一次遍历到 ‘a’：charCount['a'] = 2 > 0，减 1，charCount['a'] = 1
• 第二次遍历到 ‘a’：charCount['a'] = 1 > 0，减 1，charCount['a'] = 0
• 遍历完成，返回true

如果ransomNote = "aa"，magazine = "ab"：

• 第一次遍历到 ‘a’：charCount['a'] = 1 > 0，减 1，charCount['a'] = 0
• 第二次遍历到 ‘a’：charCount['a'] = 0，不满足count > 0，返回false

4. 为什么这样能解决问题？

这个算法的核心思想是：

• 用字典统计magazine中每个字符的可用数量
• 遍历ransomNote时，每使用一个字符，就从可用数量中减去 1
• 如果某个字符的可用数量变成 0 或负数，说明不够用了，返回false
• 如果所有字符都够用，返回true

5. 优化：提前返回

如果ransomNote的长度大于magazine的长度，肯定无法构成，可以提前返回：

classSolution{funccanConstruct(_ransomNote:String,_magazine:String)->Bool{// 优化：如果 ransomNote 比 magazine 长，肯定无法构成ifransomNote.count>magazine.count{returnfalse}varcharCount:[Character:Int]=[:]forcharinmagazine{charCount[char,default:0]+=1}forcharinransomNote{ifletcount=charCount[char],count>0{charCount[char]=count-1}else{returnfalse}}returntrue}}

这个优化可以避免不必要的计算，提高效率。

示例测试及结果

让我们用几个例子来测试一下这个解决方案：

示例 1：ransomNote = “a”, magazine = “b”

letsolution=Solution()letresult1=solution.canConstruct("a","b")print("示例 1 结果:\(result1)")// 输出: false

执行过程分析：

1. 统计magazine：charCount = ['b': 1]
2. 遍历ransomNote：
   • 字符 ‘a’：charCount['a']不存在，返回false

结果：false，因为magazine中没有字符 ‘a’。

示例 2：ransomNote = “aa”, magazine = “ab”

letresult2=solution.canConstruct("aa","ab")print("示例 2 结果:\(result2)")// 输出: false

执行过程分析：

1. 统计magazine：charCount = ['a': 1, 'b': 1]
2. 遍历ransomNote：
   • 第一次字符 ‘a’：charCount['a'] = 1 > 0，减 1，charCount['a'] = 0
   • 第二次字符 ‘a’：charCount['a'] = 0，不满足count > 0，返回false

结果：false，因为magazine中只有 1 个 ‘a’，但ransomNote需要 2 个 ‘a’。

示例 3：ransomNote = “aa”, magazine = “aab”

letresult3=solution.canConstruct("aa","aab")print("示例 3 结果:\(result3)")// 输出: true

执行过程分析：

1. 统计magazine：charCount = ['a': 2, 'b': 1]
2. 遍历ransomNote：
   • 第一次字符 ‘a’：charCount['a'] = 2 > 0，减 1，charCount['a'] = 1
   • 第二次字符 ‘a’：charCount['a'] = 1 > 0，减 1，charCount['a'] = 0
3. 遍历完成，返回true

结果：true，因为magazine中有 2 个 ‘a’，足够构成ransomNote。

示例 4：ransomNote = “abc”, magazine = “aabbcc”

letresult4=solution.canConstruct("abc","aabbcc")print("示例 4 结果:\(result4)")// 输出: true

执行过程分析：

1. 统计magazine：charCount = ['a': 2, 'b': 2, 'c': 2]
2. 遍历ransomNote：
   • 字符 ‘a’：charCount['a'] = 2 > 0，减 1，charCount['a'] = 1
   • 字符 ‘b’：charCount['b'] = 2 > 0，减 1，charCount['b'] = 1
   • 字符 ‘c’：charCount['c'] = 2 > 0，减 1，charCount['c'] = 1
3. 遍历完成，返回true

结果：true，所有字符都有足够的数量。

示例 5：ransomNote = “aabb”, magazine = “ab”

letresult5=solution.canConstruct("aabb","ab")print("示例 5 结果:\(result5)")// 输出: false

执行过程分析：

1. 优化检查：ransomNote.count = 4 > magazine.count = 2，提前返回false

结果：false，因为ransomNote比magazine长，肯定无法构成。

时间复杂度

让我们分析一下这个算法的时间复杂度：

时间复杂度：O(m + n)

其中：

• m是magazine的长度
• n是ransomNote的长度

分析：

1. 统计magazine中的字符：需要遍历magazine一次，时间复杂度 O(m)
2. 检查ransomNote中的字符：需要遍历ransomNote一次，时间复杂度 O(n)
3. 字典操作：字典的查找、插入、更新操作平均时间复杂度都是 O(1)

所以总时间复杂度是 O(m + n)。

对于题目约束（ransomNote.length, magazine.length <= 10^5），这个时间复杂度是完全可接受的。

空间复杂度

让我们分析一下这个算法的空间复杂度：

空间复杂度：O(k)

其中k是magazine中不同字符的个数。

分析：

我们使用了一个字典来存储每个字符的出现次数。字典的大小取决于magazine中不同字符的个数。

由于题目提示ransomNote和magazine由小写英文字母组成，所以最多只有 26 个不同的字符。因此，空间复杂度实际上是 O(26) = O(1)。

但在一般情况下，如果字符集更大，空间复杂度就是 O(k)，其中 k 是不同字符的个数。

实际应用场景

这种字符计数的方法在实际开发中应用非常广泛：

场景一：文本分析

在文本分析中，我们经常需要统计字符或单词的出现次数：

funcanalyzeText(_text:String)->[Character:Int]{varcharCount:[Character:Int]=[:]forcharintext{charCount[char,default:0]+=1}returncharCount}

场景二：拼写检查

在拼写检查中，我们需要检查一个单词能否由给定的字母组成：

funccanSpell(_word:String,with letters:String)->Bool{varletterCount:[Character:Int]=[:]forletterinletters{letterCount[letter,default:0]+=1}forcharinword{ifletcount=letterCount[char],count>0{letterCount[char]=count-1}else{returnfalse}}returntrue}

场景三：资源分配

在资源分配中，我们需要检查是否有足够的资源来完成某个任务：

funccanAllocate(_requirements:[String:Int],_available:[String:Int])->Bool{for(resource,needed)inrequirements{ifletavailableCount=available[resource],availableCount>=needed{continue}else{returnfalse}}returntrue}

场景四：字符频率分析

在密码学或数据分析中，我们需要分析字符的频率：

funccharacterFrequency(_text:String)->[(Character,Int)]{varfrequency:[Character:Int]=[:]forcharintext{frequency[char,default:0]+=1}returnfrequency.sorted{$0.value>$1.value}}

场景五：字谜游戏

在字谜游戏中，我们需要检查一个单词能否由给定的字母组成：

funccanFormWord(_word:String,from letters:String)->Bool{ifword.count>letters.count{returnfalse}varletterCount:[Character:Int]=[:]forletterinletters{letterCount[letter,default:0]+=1}forcharinword{ifletcount=letterCount[char],count>0{letterCount[char]=count-1}else{returnfalse}}returntrue}

总结

这道题虽然看起来简单，但实际上涉及了一个很重要的算法思想：字符计数。通过统计字符的出现次数，我们可以高效地解决很多字符串相关的问题。

关键点总结：

1. 字符计数：使用字典统计每个字符的出现次数
2. 逐个检查：遍历目标字符串，检查每个字符是否都有足够的数量
3. 及时返回：如果某个字符不够，立即返回false
4. 优化技巧：如果目标字符串比源字符串长，可以提前返回

算法优势：

1. 时间复杂度低：只需要遍历两个字符串各一次，O(m + n)
2. 空间复杂度低：只需要一个字典，O(k)，对于小写字母来说就是 O(1)
3. 实现简单：代码逻辑清晰，容易理解和维护

实际应用：

字符计数的方法在很多场景中都有应用，比如文本分析、拼写检查、资源分配、字符频率分析、字谜游戏等。掌握这种方法，可以帮助我们解决很多类似的问题。