383.赎金信.md

383. 赎金信

题目描述

给你两个字符串：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 <= 105 ransomNote 和 magazine 由小写英文字母组成

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/ransom-note

解题思路

这道题和242.有效的字母异位词思路一样

• 先记录字典magazine有哪些字母并且出现了多少次,
• 再遍历ransomNote里的字母， 检查magazine里是否有 并且val是否大于0

代码如下

func canConstruct(ransomNote string, magazine string) bool {
    hashMap := make([]int, 26)

    for _, v := range magazine {
        hashMap[v-'a']++
    }

    for _, v := range ransomNote {
        if hashMap[v-'a'] <= 0 {
            return false
        }
        hashMap[v-'a']--
    }

    return true
}

复杂度分析

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

ransomNote的长度m 和 magazine的长度n 最坏都需要遍历一次

空间复杂度：O(1)

26个字母的常数长度的数组