当前位置： 面试刷题>> 赎金信(经典算法150题)
### 题目描述
**赎金信问题**：给定两个字符串，`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 示例代码
```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 示例代码
```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 示例代码
```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个小写字母的计数。这种方法简洁且高效，适用于解决此类问题。