给定一个赎金信 (ransom
) 字符串和一个杂志(magazine
)字符串,判断第一个字符串 ransom
能不能由第二个字符串 magazines
里面的字符构成。如果可以构成,返回 true
;否则返回 false
。
(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
示例 1:
输入:ransomNote = "a", magazine = "b" 输出:false
示例 2:
输入:ransomNote = "aa", magazine = "ab" 输出:false
示例 3:
输入:ransomNote = "aa", magazine = "aab" 输出:true
提示:
- 你可以假设两个字符串均只含有小写字母。
用一个数组或字典 chars 存放 magazine 中每个字母出现的次数。遍历 ransomNote 中每个字母,判断 chars 是否包含即可。
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
counter = Counter(magazine)
for c in ransomNote:
if counter[c] <= 0:
return False
counter[c] -= 1
return True
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] counter = new int[26];
for (char c : magazine.toCharArray()) {
++counter[c - 'a'];
}
for (char c : ransomNote.toCharArray()) {
if (counter[c - 'a'] <= 0) {
return false;
}
--counter[c - 'a'];
}
return true;
}
}
function canConstruct(ransomNote: string, magazine: string): boolean {
let counter = new Array(26).fill(0);
let base = 'a'.charCodeAt(0);
for (let s of magazine) {
++counter[s.charCodeAt(0) - base];
}
for (let s of ransomNote) {
let idx = s.charCodeAt(0) - base;
if (counter[idx] == 0) return false;
--counter[idx];
}
return true;
};
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int> counter(26);
for (char c : magazine) ++counter[c - 'a'];
for (char c : ransomNote)
{
if (counter[c - 'a'] <= 0) return false;
--counter[c - 'a'];
}
return true;
}
};
func canConstruct(ransomNote string, magazine string) bool {
rc := make([]int, 26)
for _, b := range ransomNote {
rc[b-'a']++
}
mc := make([]int, 26)
for _, b := range magazine {
mc[b-'a']++
}
for i := 0; i < 26; i++ {
if rc[i] > mc[i] {
return false
}
}
return true
}