算法题
哈希表(hash map)
赎金信

赎金信

题目

给你两个字符串: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
}