题目描述
赎金信问题:给定两个字符串,ransomNote
(赎金信)和magazine
(杂志)。ransomNote
字符串的每一个字母都恰好对应 magazine
字符串中的某个字母,但不一定按相同的顺序。判断 ransomNote
是否可以由 magazine
中的字符重新排列得到。
注意:
- 你可以假设
magazine
字符串足够长,以包含ransomNote
字符串中的所有字符。 magazine
和ransomNote
只包含小写字母。
示例
示例 1:
输入: ransomNote = "a", magazine = "b"
输出: false
示例 2:
输入: ransomNote = "aa", magazine = "ab"
输出: false
示例 3:
输入: ransomNote = "aa", magazine = "aab"
输出: true
PHP 示例代码
function canConstruct($ransomNote, $magazine) {
$count = array_fill(0, 26, 0); // 初始化一个长度为26的数组用于计数,对应26个小写字母
// 统计magazine中每个字符的出现次数
for ($i = 0; $i < strlen($magazine); $i++) {
$count[ord($magazine[$i]) - ord('a')]++;
}
// 检查ransomNote中的每个字符是否都能在magazine中找到足够的数量
for ($i = 0; $i < strlen($ransomNote); $i++) {
$index = ord($ransomNote[$i]) - ord('a');
if ($count[$index] === 0) {
return false;
}
$count[$index]--;
}
return true;
}
// 示例用法
$ransomNote = "aa";
$magazine = "aab";
echo canConstruct($ransomNote, $magazine) ? "true" : "false"; // 输出 true
Python 示例代码
def canConstruct(ransomNote, magazine):
count = [0] * 26 # 初始化一个长度为26的列表用于计数
# 统计magazine中每个字符的出现次数
for char in magazine:
count[ord(char) - ord('a')] += 1
# 检查ransomNote中的每个字符是否都能在magazine中找到足够的数量
for char in ransomNote:
index = ord(char) - ord('a')
if count[index] == 0:
return False
count[index] -= 1
return True
# 示例用法
ransomNote = "aa"
magazine = "aab"
print(canConstruct(ransomNote, magazine)) # 输出 True
JavaScript 示例代码
function canConstruct(ransomNote, magazine) {
const count = new Array(26).fill(0); // 初始化一个长度为26的数组用于计数
// 统计magazine中每个字符的出现次数
for (let char of magazine) {
const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
count[index]++;
}
// 检查ransomNote中的每个字符是否都能在magazine中找到足够的数量
for (let char of ransomNote) {
const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
if (count[index] === 0) {
return false;
}
count[index]--;
}
return true;
}
// 示例用法
const ransomNote = "aa";
const magazine = "aab";
console.log(canConstruct(ransomNote, magazine)); // 输出 true
在这些示例中,我们使用了字符的ASCII码值来索引数组,从而实现了对26个小写字母的计数。这种方法简洁且高效,适用于解决此类问题。