赎金信
难度:
标签:
题目描述
给你两个字符串: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
由小写英文字母组成
代码结果
运行时间: 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字符串来检查每个字符?
▷🦆
题解中提到将set转换为list,这一转换步骤是否必须,它对算法的效率有什么影响?
▷🦆
在题解的方法中,ransomNote和magazine的count函数多次调用是否会影响性能,能否有更高效的方法来统计字符出现次数?
▷🦆
题解中如果magazine字符串很长但ransomNote较短,这种算法效率如何,有没有更优的处理方式?
▷相关问题
贴纸拼词
我们有 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
由小写英文单词组成