383.赎金信

一、问题描述

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

示例：

输入：ransomNote = "a", magazine = "b"
输出：false
输入：ransomNote = "aa", magazine = "ab"
输出：false
输入：ransomNote = "aa", magazine = "aab"
输出：true

二、方案一：计数法

1、思路

使用两个数组（或哈希表）分别统计赎金信和杂志中每个字符的出现次数。然后比较赎金信中的每个字符在杂志中的出现次数是否足够。

2、代码实现

func canConstruct(ransomNote string, magazine string) bool {
    ransomCount := [26]int{}
    magazineCount := [26]int{}
    
    for _, ch := range ransomNote {
        ransomCount[ch-'a']++
    }
    for _, ch := range magazine {
        magazineCount[ch-'a']++
    }
    
    for i := 0; i < 26; i++ {
        if ransomCount[i] > magazineCount[i] {
            return false
        }
    }
    return true
}

3、复杂度分析

• 时间复杂度：O(n + m)，其中 n 是赎金信的长度，m 是杂志的长度。
• 空间复杂度：O(1)，因为我们只使用了固定大小的数组来存储字符计数。

三、方案二：哈希表法

1、思路

使用哈希表来存储杂志中每个字符的出现次数。然后遍历赎金信中的每个字符，检查它在杂志中的出现次数是否大于等于 1。如果是，则将其出现次数减 1；如果不是，则返回 false。

2、代码实现

func canConstruct(ransomNote string, magazine string) bool {
    magazineCount := make(map[rune]int)
    
    for _, ch := range magazine {
        magazineCount[ch]++
    }
    
    for _, ch := range ransomNote {
        if count, ok := magazineCount[ch]; ok && count > 0 {
            magazineCount[ch]--
        } else {
            return false
        }
    }
    return true
}

3、复杂度分析

• 时间复杂度：O(n + m)，其中 n 是赎金信的长度，m 是杂志的长度。
• 空间复杂度：O(m)，因为我们需要存储杂志中每个字符的出现次数。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
计数法	O(n + m)	O(1)	实现简单，空间效率高	只适用于小写英文字符
哈希表法	O(n + m)	O(m)	适用于任意字符集	需要额外空间

推荐使用计数法，因为它在空间效率上更优，并且此题只涉及小写英文字符。如果字符集更广泛，哈希表法将是更好的选择。