TNotes.leetcode

Appearance

0383. 赎金信【简单】

0383. 赎金信【简单】 ​

1. 📝 题目描述 ​

给你两个字符串：ransomNote 和 magazine，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

txt
输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

txt
输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

txt
输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

  • 1 <= ransomNote.length, magazine.length <= 10^5
  • ransomNote 和 magazine 由小写英文字母组成

2. 🎯 s.1 - arr ​

js
/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function (ransomNote, magazine) {
  // 统计杂志中每个字符的出现次数
  const charCount = new Array(26).fill(0)

  // 遍历杂志字符串，统计字符频次
  for (const char of magazine) {
    charCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++
  }

  // 遍历赎金信字符串，检查字符是否足够
  for (const char of ransomNote) {
    const index = char.charCodeAt(0) - 'a'.charCodeAt(0)
    if (charCount[index] === 0) {
      // 字符数量不足，无法构造
      return false
    }
    // 使用一个字符，对应计数减 1
    charCount[index]--
  }

  return true
}
  • 时间复杂度：O(m+n)，其中 m 是杂志字符串长度，n 是赎金信字符串长度
  • 空间复杂度：O(1)，使用了固定大小的数组（26 个字母）

3. 🎯 s.2 - map ​

js
/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function (ransomNote, magazine) {
  const map = new Map()

  // 统计杂志字符频次
  for (const char of magazine) {
    map.set(char, (map.get(char) || 0) + 1)
  }

  // 检查赎金信字符需求
  for (const char of ransomNote) {
    if (!map.has(char) || map.get(char) === 0) {
      return false
    }
    map.set(char, map.get(char) - 1)
  }

  return true
}
  • 时间复杂度：O(m+n)，其中 m 是杂志字符串长度，n 是赎金信字符串长度，需要遍历两个字符串各一次。
  • 空间复杂度：O(k)，其中 k 是杂志中不同字符的个数，最坏情况下需要存储杂志中所有不同的字符及其频次。

Discussions