Ransom Note（赎金信）

题目 / Problem

中文： 给定两个字符串 ransomNote 和 magazine，判断能否使用 magazine 中的字母构造出 ransomNote。如果可以，返回 true；否则返回 false。

magazine 中的每个字母在 ransomNote 中最多只能使用一次。

English: Given two strings ransomNote and magazine, return true if ransomNote can be constructed using the letters from magazine, and false otherwise.

Each letter in magazine can be used only once in ransomNote.

示例 / Examples

Example 1

Input:  ransomNote = "a", magazine = "b"
Output: false

magazine 中没有字母 a，因此无法构造 ransomNote。
The magazine does not contain the letter a, so the ransom note cannot be constructed.

Example 2

Input:  ransomNote = "aa", magazine = "ab"
Output: false

ransomNote 需要两个 a，但 magazine 中只有一个 a。
The ransom note needs two occurrences of a, but the magazine contains only one.

Example 3

Input:  ransomNote = "aa", magazine = "aab"
Output: true

magazine 中有两个 a，足以构造 ransomNote。
The magazine contains two occurrences of a, which is enough to construct the ransom note.

约束 / Constraints

1 <= ransomNote.length, magazine.length <= 10⁵
ransomNote 和 magazine 仅由小写英文字母组成。
ransomNote and magazine consist of lowercase English letters.

解题思路：字符计数 / Approach: Character Counting

由于输入只包含 26 个小写英文字母，可以使用长度为 26 的数组记录 magazine 中每个字母可使用的次数。
Because the inputs contain only the 26 lowercase English letters, use a fixed array of length 26 to record how many times each magazine letter is available.

如果 ransomNote 比 magazine 长，字符一定不够，直接返回 false。
If ransomNote is longer than magazine, there cannot be enough characters, so return false immediately.
遍历 magazine，增加每个字母的可用次数。
Traverse magazine and increment the available count for each letter.
遍历 ransomNote，每使用一个字母，就将对应计数减一。
Traverse ransomNote and decrement the corresponding count whenever a letter is used.
如果某个计数减到负数，说明该字母的需求量超过库存，返回 false。
If a count becomes negative, demand for that letter exceeds the supply, so return false.
如果所有字符都能取得，返回 true。
If every required character is available, return true.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
function canConstruct(ransomNote, magazine) {
  if (ransomNote.length > magazine.length) {
    return false;
  }

  const counts = new Array(26).fill(0);
  const codeA = 'a'.charCodeAt(0);

  for (let i = 0; i < magazine.length; i++) {
    const index = magazine.charCodeAt(i) - codeA;
    counts[index]++;
  }

  for (let i = 0; i < ransomNote.length; i++) {
    const index = ransomNote.charCodeAt(i) - codeA;
    counts[index]--;

    if (counts[index] < 0) {
      return false;
    }
  }

  return true;
}

执行过程 / Walkthrough

以 ransomNote = "aa"、magazine = "aab" 为例：
For ransomNote = "aa" and magazine = "aab":

统计杂志字符 / Count Magazine Characters

magazine = "aab"

a: 2
b: 1

消耗赎金信字符 / Consume Ransom Note Characters

需要的字符 / Required	使用前计数 / Before	使用后计数 / After	结果 / Result
第一个 `a` / First `a`	2	1	可用 / Available
第二个 `a` / Second `a`	1	0	可用 / Available

所有需要的字符都有足够库存，因此返回 true。
Every required character has sufficient supply, so return true.

对于 ransomNote = "aa"、magazine = "ab"，第二次使用 a 时计数会从 0 变为 -1，因此返回 false。
For ransomNote = "aa" and magazine = "ab", the count for a changes from 0 to -1 when the second a is consumed, so return false.

复杂度 / Complexity

设 ransomNote 的长度为 r，magazine 的长度为 m。
Let r be the length of ransomNote and m the length of magazine.

时间复杂度：O(r + m)，两个字符串各遍历一次。
Time: O(r + m), because each string is traversed once.
空间复杂度：O(1)，计数数组始终只有 26 个元素。
Space: O(1), because the frequency array always contains only 26 elements.

使用 Map 的通用解法 / General Map Approach

如果输入字符范围不固定，可以使用 Map 保存字符频率：
If the character set is not fixed, a Map can store character frequencies:

function canConstructWithMap(ransomNote, magazine) {
  if (ransomNote.length > magazine.length) {
    return false;
  }

  const counts = new Map();

  for (const char of magazine) {
    counts.set(char, (counts.get(char) ?? 0) + 1);
  }

  for (const char of ransomNote) {
    const remaining = counts.get(char) ?? 0;

    if (remaining === 0) {
      return false;
    }

    counts.set(char, remaining - 1);
  }

  return true;
}

时间复杂度 / Time: O(r + m)（假设哈希表操作平均为 O(1)）
Assuming average O(1) hash-map operations.
空间复杂度 / Space: O(k)，其中 k 是 magazine 中不同字符的数量。
k is the number of distinct characters in magazine.

在本题只包含小写英文字母的约束下，固定数组更简单，且额外空间为常数。
Under this problem's lowercase-English-letter constraint, the fixed array is simpler and uses constant extra space.

易错点 / Common Pitfalls

必须统计字符出现次数，不能只判断字符是否存在。
Count character occurrences; checking only whether a character exists is insufficient.
magazine 中的每个字符只能使用一次，使用后必须减少库存。
Each magazine character can be used only once, so its available count must be decremented.
当某个字符库存不足时，可以立即返回 false，无需继续遍历。
Return false immediately when a character's supply is insufficient.
ransomNote.length > magazine.length 时一定无法构造。
Construction is impossible when ransomNote.length > magazine.length.
固定长度为 26 的数组只适用于题目限定的小写英文字母。
A fixed 26-element array applies only to the constrained lowercase English alphabet.

Ransom Note