LeetCode每日一题

今天的每日一题是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 由小写英文字母组成

思路分析

把字符串中每一个字符映射到哈希表上，统计数字，如果ransomNote中的对应字母数量小于magazine就可以返回true。

优化点：如果ransomNote长度大于magazine了，则直接返回false。

代码

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if(ransomNote.length() > magazine.length()) return false;
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();
        for (char c : ransomNote.toCharArray()) {
            map1.put(c, map1.getOrDefault(c, 0) + 1);
        }

        for (char c : magazine.toCharArray()) {
            map2.put(c, map2.getOrDefault(c, 0) + 1);
        }

        for (char key : map1.keySet()) {
            if (!map2.containsKey(key) || map2.get(key) < map1.get(key)) {
                return false;
            }
        }
        return true;
    }
}

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine):
            return False
        tab1, tab2 = Counter(ransomNote), Counter(magazine)
        for key in tab1:
            if tab2[key] < tab1[key]:
                return False
        return True

复杂度分析

时间复杂度：O(m+n)，n和m是两个字符串的长度。
空间复杂度：O(s)，s为字符数量。