Valid Anagram（有效的字母异位词）

题目 / Problem

中文： 给定两个字符串 s 和 t，如果 t 是 s 的字母异位词，返回 true；否则返回 false。

字母异位词由重新排列原字符串中的所有字符得到，每个字符的出现次数必须完全相同。
An anagram is formed by rearranging all characters of the original string, with every character appearing the same number of times.

English: Given two strings s and t, return true if t is an anagram of s, and false otherwise.

示例 / Examples

Example 1

Input:  s = "anagram", t = "nagaram"
Output: true

Example 2

Input:  s = "rat", t = "car"
Output: false

约束 / Constraints

1 <= s.length, t.length <= 5 × 10⁴
s 和 t 仅由小写英文字母组成。
s and t consist of lowercase English letters.

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

两个字符串互为字母异位词需要同时满足：
For two strings to be anagrams, both conditions must hold:

字符串长度相同。
The strings have the same length.
每个字符在两个字符串中的出现次数相同。
Every character appears the same number of times in both strings.

题目保证字符串只包含 26 个小写英文字母，因此可以使用长度为 26 的数组记录字符频率：
Because the strings contain only the 26 lowercase English letters, a fixed array of length 26 can store the character frequencies:

如果两个字符串长度不同，立即返回 false。
If their lengths differ, return false immediately.
遍历 s，将对应字符的计数加一。
Traverse s and increment the count for each character.
遍历 t，将对应字符的计数减一。
Traverse t and decrement the count for each character.
如果最终所有计数都为 0，两个字符串互为字母异位词。
If every final count is 0, the strings are anagrams.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
function isAnagram(s, t) {
  if (s.length !== t.length) {
    return false;
  }

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

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

  return counts.every((count) => count === 0);
}

执行过程 / Walkthrough

以 s = "anagram"、t = "nagaram" 为例：
For s = "anagram" and t = "nagaram":

字符 / Character	`s` 中的次数 / Count in `s`	`t` 中的次数 / Count in `t`
`a`	3	3
`n`	1	1
`g`	1	1
`r`	1	1
`m`	1	1

所有字符的计数差值都为 0，因此返回 true。
Every character has a frequency difference of 0, so the function returns true.

对于 s = "rat"、t = "car"，字符 t 和 c 的计数不同，因此返回 false。
For s = "rat" and t = "car", the counts of t and c differ, so the function returns false.

复杂度 / Complexity

设两个字符串的长度均为 n。
Let both strings have length n.

时间复杂度：O(n)，每个字符只处理一次。
Time: O(n), because every character is processed once.
空间复杂度：O(1)，计数数组始终只有 26 个元素。
Space: O(1), because the frequency array always contains only 26 elements.

排序解法 / Sorting Approach

也可以将两个字符串的字符分别排序，再比较排序后的结果：
The characters of both strings can also be sorted and the sorted results compared:

function isAnagramBySorting(s, t) {
  if (s.length !== t.length) {
    return false;
  }

  return [...s].sort().join('') === [...t].sort().join('');
}

时间复杂度 / Time: O(n log n)
空间复杂度 / Space: O(n)，需要创建字符数组和排序后的字符串。
Character arrays and sorted strings require additional space.

字符计数解法的时间复杂度更低，是本题约束下的更优选择。
Character counting has a lower time complexity and is preferable under the given constraints.

进阶：Unicode 字符 / Follow-up: Unicode Characters

如果输入可能包含 Unicode 字符，就不能再使用固定长度为 26 的数组。可以使用 Map 保存每个字符的出现次数。
If the inputs may contain Unicode characters, a fixed array of length 26 is no longer sufficient. Use a Map to store the frequency of each character.

JavaScript 的 for...of 会按 Unicode 码点遍历字符串，比按 UTF-16 代码单元索引更适合处理基本的 Unicode 字符。
JavaScript's for...of iterates over Unicode code points, making it more suitable than UTF-16 code-unit indexing for basic Unicode handling.

function isUnicodeAnagram(s, t) {
  const charsS = [...s.normalize('NFC')];
  const charsT = [...t.normalize('NFC')];

  if (charsS.length !== charsT.length) {
    return false;
  }

  const counts = new Map();

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

  for (const char of charsT) {
    const remaining = counts.get(char);

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

    if (remaining === 1) {
      counts.delete(char);
    } else {
      counts.set(char, remaining - 1);
    }
  }

  return counts.size === 0;
}

normalize('NFC') 可以统一某些视觉上相同但编码方式不同的字符，例如预组合字符与组合字符序列。
normalize('NFC') makes some visually identical characters use a consistent representation, such as precomposed characters and combining-character sequences.

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

易错点 / Common Pitfalls

只比较两个字符串包含哪些字符是不够的，还必须比较每个字符的出现次数。
Comparing only which characters appear is insufficient; their frequencies must also match.
两个字符串长度不同，一定不可能互为字母异位词。
Strings with different lengths cannot be anagrams.
不要使用普通对象时忘记处理原型属性；固定数组或 Map 更安全。
When using a plain object, do not overlook inherited properties; a fixed array or Map is safer.
固定的 26 位计数数组只适用于小写英文字母。
A fixed 26-element frequency array works only for lowercase English letters.
Unicode 文本可能存在不同的规范化形式，必要时应先调用 normalize()。
Unicode text can have different normalization forms, so call normalize() when appropriate.

Valid Anagram