题目描述
给你两个字符串: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 <= 10^5
- ransomNote 和 magazine 由小写英文字母组成
题目地址:https://leetcode.com/problems/ransom-note/
题目大意
判断 ransom 能否由 magazines 的字符构成。
解题方法
理解题意很关键,这个是说从 magazine 中取出几个元素排列组合能够摆成 ransomNote,所以可以说 ransomNote 是 magazine 的子集。
字符串是否包含/子集的问题,统统用统计词频来做。既然是子集,那么 ransomNote 中每个字符出现的次数都应该小于等于该字符在 magazine 出现的次数。
统计词频有两种方法:哈希表(字典)或者数组。
哈希表(字典)
下面是 Python 解法,可以直接用 Counter 统计词频。
然后判断 ransomNote 的每个字符出现次数都小于等于其在 ransomNote 的出现次数。
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
noteCount = collections.Counter(ransomNote)
magaCount = collections.Counter(magazine)
for note in noteCount:
if magaCount[note] < noteCount[note]:
return False
return True
- 时间复杂度:$O(N)$
- 空间复杂度:$O(N)$
数组
因为题目中说了只包含了小写字母,所以可以用有 26 个位置的数组,保存字符出现的次数。
如果使用类似于上面哈希表(字典)的解法,那么需要两个数组。
其实可以用一个数组就够了:
- 先遍历 magazine 的字符,使其在数组中对应位置++;
- 然后再遍历 ransomNote 的字符,使其在数组中对应位置–;
- 如果在发现 — 之后,元素出现的个数小于 0 了,则说明该字符在 magazine 中出现的频率小于在 ransomNote 出现的频率,返回 False。
public class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length() > magazine.length())
return false;
int []chars= new int[26];
for(int i=0; i< magazine.length(); i++){
chars[magazine.charAt(i)- 'a']++;
}
for(int i=0; i< ransomNote.length(); i++){
chars[ransomNote.charAt(i)- 'a']--;
if(chars[ransomNote.charAt(i)- 'a'] < 0){
return false;
}
}
return true;
}
}
- 时间复杂度:$O(N)$
- 空间复杂度:$O(N)$
© 版权声明
文章版权归作者所有,未经允许请勿转载。
暂无评论内容