赎金信
题目
给你两个字符串：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思路
这道题目是求字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。
本题判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成，但是这里需要注意两点。
- 第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。
- 第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，这一点很重要
两个解法：
- 暴力解法：第一个思路其实就是暴力枚举了，两层for循环，不断去寻找
- 哈希解法：题目说只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组来记录magazine里字母出现的次数，然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。
解法
暴力解法
func canConstruct(ransomNote string, magazine string) bool {
for i := 0; i < len(ransomNote); i++ {
// 寻找ransomNote[i]在magazine中的位置
index := strings.Index(magazine, string(ransomNote[i]))
if index == -1 {
return false
}
// 删除magazine中的这个字符
magazine = magazine[:index] + magazine[index+1:]
}
return true
}哈希解法
func canConstruct(ransomNote string, magazine string) bool {
m := make(map[byte]int)
// 统计magazine中每个字符出现的次数
for i := 0; i < len(magazine); i++ {
m[magazine[i]]++
}
// 遍历ransomNote，判断magazine中是否包含ransomNote的字符
for i := 0; i < len(ransomNote); i++ {
if m[ransomNote[i]] == 0 {
return false
}
m[ransomNote[i]]--
}
return true
}