LeetCode383 赎金信

发表于

这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战。

题目描述：

383. 赎金信 - 力扣（LeetCode） (leetcode-cn.com)

为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。

给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。

如果可以构成，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例一

1
2
ini复制代码输入： ransomNote = "a", magazine = "b"
输出： false

示例二

1
2
ini复制代码输入： ransomNote = "aa", magazine = "ab"
输出： false

示例三

1
2
ini复制代码输入： ransomNote = "aa", magazine = "aab"
输出： true

提示：

  • 1 <= ransomNote.length, magazine.length <= 10^5
  • ransomNote 和 magazine 由小写英文字母组成

思路分析

哈希表

别看题目说的花里胡哨的，其实就是要看 赎金信 中的字母在杂志中能不能都找出来。数学上来说就是子集的概念而已。

明白了题意，我们就很容易想到哈希表的解法了，我们可以利用hash表记录 杂志 中每个字母的个数，也就是我们有的字母，然后遍历 赎金信 的时候，每找到一个就减掉个数，如果出现 负数， 说明我们的 杂志 已经不能满足我们的需求了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Kotlin复制代码class Solution {
    fun canConstruct(ransomNote: String, magazine: String): Boolean {
        val bucket = IntArray(26)

        for (c in magazine) {
            bucket[c - 'a']++
        }

        for (c in ransomNote) {
            if (bucket[c - 'a'] <= 0) {
                return false
            }
            bucket[c - 'a']--
        }

        return true
    }
        
}

总结

每日简单一题。

参考

小白简单思路 - 赎金信 - 力扣（LeetCode） (leetcode-cn.com)

python3 Counter永远的神，使用“与”操作，极少代码解决问题 - 赎金信 - 力扣（LeetCode） (leetcode-cn.com)

哈希 - 赎金信 - 力扣（LeetCode） (leetcode-cn.com)

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%