当前位置: 面试刷题>> 赎金信(经典算法150题)


题目描述

赎金信问题:给定两个字符串,ransomNote(赎金信)和magazine(杂志)。ransomNote 字符串的每一个字母都恰好对应 magazine 字符串中的某个字母,但不一定按相同的顺序。判断 ransomNote 是否可以由 magazine 中的字符重新排列得到。

注意

  • 你可以假设 magazine 字符串足够长,以包含 ransomNote 字符串中的所有字符。
  • magazineransomNote 只包含小写字母。

示例

示例 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个小写字母的计数。这种方法简洁且高效,适用于解决此类问题。

推荐面试题