赎金信
题目
给你两个字符串: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
}