leetcode
leetcode 351 ~ 400
赎金信

赎金信

难度:

标签:

题目描述

给你两个字符串:ransomNotemagazine ,判断 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
  • ransomNotemagazine 由小写英文字母组成

代码结果

运行时间: 20 ms, 内存: 16.5 MB


/*
 * 题目思路:
 * 使用 Java Stream 和 Map 来解决此问题。
 * 我们可以将 magazine 中的字符计数存储在 Map 中,
 * 然后使用 Stream 检查 ransomNote 中的字符是否都可以找到。
 */
 
import java.util.Map;
import java.util.stream.Collectors;
 
public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Long> magazineMap = magazine.chars()
            .mapToObj(c -> (char) c)
            .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
        // 使用 Stream 检查 ransomNote 中的字符
        return ransomNote.chars()
            .mapToObj(c -> (char) c)
            .allMatch(c -> magazineMap.merge(c, -1L, Long::sum) >= 0);
    }
}

解释

方法:

该题解的思路是:首先用set去重获得ransomNote中的所有不重复字符,然后遍历这些字符,检查每个字符是否在magazine中出现,并且在ransomNote中出现的次数是否小于等于在magazine中出现的次数。如果检查通过,则返回True,否则返回False。

时间复杂度:

O(mn)

空间复杂度:

O(m)

代码细节讲解

🦆
为什么题解中选择先将ransomNote中的字符去重,而不是直接遍历ransomNote字符串来检查每个字符?
题解中选择先去重是为了减少不必要的重复检查。如果直接遍历ransomNote字符串,对于每个字符都会重复计算其在ransomNote和magazine中的出现次数,尤其是对于重复字符,这将导致不必要的性能浪费。通过去重,可以确保每个字符只被检查一次,从而提高效率。
🦆
题解中提到将set转换为list,这一转换步骤是否必须,它对算法的效率有什么影响?
将set转换为list这一步骤在本题中不是必须的,因为遍历set和遍历list的效率在这种情况下差别不大。set本身已经提供了必要的不重复性质和可遍历性。转换为list主要是为了在某些情况下需要对元素进行排序或其他特定操作时使用,但在这个算法中并不需要这些操作,因此这一步骤可以省略以优化性能。
🦆
在题解的方法中,ransomNote和magazine的count函数多次调用是否会影响性能,能否有更高效的方法来统计字符出现次数?
在题解的方法中,每次检查一个字符时调用count函数将会对整个字符串进行遍历,这导致算法的时间复杂度较高。一个更高效的方法是首先使用哈希表(如Python中的字典)来统计ransomNote和magazine中每个字符的出现次数。这样,每个字符的出现次数只计算一次,之后可以直接从字典中获取,大大提高效率。
🦆
题解中如果magazine字符串很长但ransomNote较短,这种算法效率如何,有没有更优的处理方式?
在题解中,如果magazine字符串很长,那么每次调用count函数都将遍历整个magazine字符串,这会导致算法效率降低。一个更优的处理方式是先统计magazine中每个字符的出现次数存入字典,然后遍历ransomNote中的字符,直接从字典中读取次数进行比较。这样可以避免重复遍历长字符串,特别是当magazine很长时,能显著提高效率。

相关问题

贴纸拼词

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ,方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意,你可以多次使用每个贴纸,每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能,则返回 -1

注意:在所有的测试用例中,所有的单词都是从 1000 个最常见的美国英语单词中随机选择的,并且 target 被选择为两个随机单词的连接。

 

示例 1:

输入: stickers = ["with","example","science"], target = "thehat"
输出:3
解释:
我们可以使用 2 个 "with" 贴纸,和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后,就可以形成目标 “thehat“ 了。
此外,这是形成目标字符串所需的最小贴纸数量。

示例 2:

输入:stickers = ["notice","possible"], target = "basicbasic"
输出:-1
解释:我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

 

提示:

  • n == stickers.length
  • 1 <= n <= 50
  • 1 <= stickers[i].length <= 10
  • 1 <= target.length <= 15
  • stickers[i] 和 target 由小写英文单词组成