0383. 赎金信 #

标签：哈希表、字符串、计数
难度：简单

题目大意 #

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

给定一个赎金信字符串 ransomNote 和一个杂志字符串 magazine。

要求：判断 ransomNote 能不能由 magazines 里面的字符构成。如果可以构成，返回 True；否则返回 False。

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

解题思路 #

暴力做法是双重循环遍历字符串 ransomNote 和 magazine。我们可以用哈希表来减少算法的时间复杂度。具体做法如下：

先用哈希表存储 magazine 中各个字符的个数（哈希表可用字典或数组实现）。
再遍历字符串 ransomNote 中每个字符，对于每个字符：
- 如果在哈希表中个数为 0，直接返回 False。
- 如果在哈希表中个数不为 0，将其个数减 1。
遍历到最后，则说明 ransomNote 能由 magazines 里面的字符构成。返回 True。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magazine_counts = [0 for _ in range(26)]

        for ch in magazine:
            num = ord(ch) - ord('a')
            magazine_counts[num] += 1

        for ch in ransomNote:
            num = ord(ch) - ord('a')
            if magazine_counts[num] == 0:
                return False
            else:
                magazine_counts[num] -= 1

        return True