给你两个字符串：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 <= 105ransomNote 和 magazine 由小写英文字母组成
方法一：字符统计
题目要求使用字符串 magazine 中的字符来构建新的字符串 ransomNote，且ransomNote 中的每个字符只能使用一次，只需要满足字符串 magazine 中的每个英文字母 $(\texttt{‘a’-‘z’})$ 的统计次数都大于等于 ransomNote 中相同字母的统计次数即可。
- 如果字符串 magazine 的长度小于字符串 ransomNote 的长度，则我们可以肯定 magazine 无法构成 ransomNote，此时直接返回 false。
- 首先统计 magazine 中每个英文字母 $a$ 的次数 cnt}[a]$，再遍历统计 ransomNote 中每个英文字母的次数，如果发现 ransomNote 中存在某个英文字母 $c$ 的统计次数大于 magazine 中该字母统计次数 cnt}[c]$，则此时我们直接返回 false。
代码
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if (ransomNote.length() > magazine.length()) {
return false;
}
int[] cnt = new int[26];
for (char c : magazine.toCharArray()) {
cnt[c - 'a']++;
}
for (char c : ransomNote.toCharArray()) {
cnt[c - 'a']--;
if(cnt[c - 'a'] < 0) {
return false;
}
}
return true;
}
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if (ransomNote.size() > magazine.size()) {
return false;
}
vector<int> cnt(26);
for (auto & c : magazine) {
cnt[c - 'a']++;
}
for (auto & c : ransomNote) {
cnt[c - 'a']--;
if (cnt[c - 'a'] < 0) {
return false;
}
}
return true;
}
};
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class Solution {
public bool CanConstruct(string ransomNote, string magazine) {
if (ransomNote.Length > magazine.Length) {
return false;
}
int[] cnt = new int[26];
foreach (char c in magazine) {
cnt[c - 'a']++;
}
foreach (char c in ransomNote) {
cnt[c - 'a']--;
if (cnt[c - 'a'] < 0) {
return false;
}
}
return true;
}
}
|
[sol1-Python3]1
2
3
4
5
| class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
if len(ransomNote) > len(magazine):
return False
return not collections.Counter(ransomNote) - collections.Counter(magazine)
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| var canConstruct = function(ransomNote, magazine) {
if (ransomNote.length > magazine.length) {
return false;
}
const cnt = new Array(26).fill(0);
for (const c of magazine) {
cnt[c.charCodeAt() - 'a'.charCodeAt()]++;
}
for (const c of ransomNote) {
cnt[c.charCodeAt() - 'a'.charCodeAt()]--;
if(cnt[c.charCodeAt() - 'a'.charCodeAt()] < 0) {
return false;
}
}
return true;
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func canConstruct(ransomNote, magazine string) bool {
if len(ransomNote) > len(magazine) {
return false
}
cnt := [26]int{}
for _, ch := range magazine {
cnt[ch-'a']++
}
for _, ch := range ransomNote {
cnt[ch-'a']--
if cnt[ch-'a'] < 0 {
return false
}
}
return true
}
|
复杂度分析
