给你两个字符串: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
由小写英文字母组成
方法一:哈希表或数组
我们可以用一个哈希表或长度为 magazine
中所有字符出现的次数。然后遍历字符串 ransomNote
,对于其中的每个字符 magazine
中出现的次数不够,因此无法构成 ransomNote
,返回
否则,遍历结束后,说明 ransomNote
中的每个字符都可以在 magazine
中找到对应的字符,因此返回
时间复杂度 ransomNote
和 magazine
的长度;而
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
cnt = Counter(magazine)
for c in ransomNote:
cnt[c] -= 1
if cnt[c] < 0:
return False
return True
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] cnt = new int[26];
for (int i = 0; i < magazine.length(); ++i) {
++cnt[magazine.charAt(i) - 'a'];
}
for (int i = 0; i < ransomNote.length(); ++i) {
if (--cnt[ransomNote.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}
}
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int cnt[26]{};
for (char& c : magazine) {
++cnt[c - 'a'];
}
for (char& c : ransomNote) {
if (--cnt[c - 'a'] < 0) {
return false;
}
}
return true;
}
};
func canConstruct(ransomNote string, magazine string) bool {
cnt := [26]int{}
for _, c := range magazine {
cnt[c-'a']++
}
for _, c := range ransomNote {
cnt[c-'a']--
if cnt[c-'a'] < 0 {
return false
}
}
return true
}
function canConstruct(ransomNote: string, magazine: string): boolean {
const cnt = new Array(26).fill(0);
for (const c of magazine) {
++cnt[c.charCodeAt(0) - 97];
}
for (const c of ransomNote) {
if (--cnt[c.charCodeAt(0) - 97] < 0) {
return false;
}
}
return true;
}
class Solution {
/**
* @param String $ransomNote
* @param String $magazine
* @return Boolean
*/
function canConstruct($ransomNote, $magazine) {
$arrM = str_split($magazine);
for ($i = 0; $i < strlen($magazine); $i++) {
$hashtable[$arrM[$i]] += 1;
}
for ($j = 0; $j < strlen($ransomNote); $j++) {
if (!isset($hashtable[$ransomNote[$j]]) || $hashtable[$ransomNote[$j]] == 0) return false;
else $hashtable[$ransomNote[$j]] -= 1;
}
return true;
}
}