有效的字母异位词

问题

给定两个字符串 s 和 t，判断 t 是否是 s 的字母异位词。

字母异位词是指由相同字母重新排列组成的单词，每个字母出现的次数相同。

示例：

• s = "anagram", t = "nagaram" → true
• s = "rat", t = "car" → false

解答

方法一：排序比较

/**
 * 排序后比较两个字符串是否相等
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
function isAnagram(s, t) {
  // 长度不同，直接返回 false
  if (s.length !== t.length) {
    return false;
  }
  
  // 将字符串转为数组，排序后再转回字符串比较
  return s.split('').sort().join('') === t.split('').sort().join('');
}

// 测试
console.log(isAnagram('anagram', 'nagaram')); // true
console.log(isAnagram('rat', 'car'));         // false

时间复杂度：O(n log n)，排序的开销。

方法二：字符计数

/**
 * 使用哈希表统计字符出现次数
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
function isAnagram(s, t) {
  if (s.length !== t.length) {
    return false;
  }
  
  const count = {};
  
  // 统计 s 中每个字符的出现次数
  for (const char of s) {
    count[char] = (count[char] || 0) + 1;
  }
  
  // 遍历 t，减少对应字符的计数
  for (const char of t) {
    if (!count[char]) {
      // 字符不存在或计数已为 0
      return false;
    }
    count[char]--;
  }
  
  return true;
}

// 测试
console.log(isAnagram('anagram', 'nagaram')); // true
console.log(isAnagram('rat', 'car'));         // false

时间复杂度：O(n)，只需遍历两次字符串。

方法三：数组计数（仅限小写字母）

/**
 * 使用固定长度数组计数，适用于只包含小写字母的情况
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
function isAnagram(s, t) {
  if (s.length !== t.length) {
    return false;
  }
  
  // 26 个字母的计数数组
  const count = new Array(26).fill(0);
  const base = 'a'.charCodeAt(0);
  
  for (let i = 0; i < s.length; i++) {
    // s 中的字符加 1，t 中的字符减 1
    count[s.charCodeAt(i) - base]++;
    count[t.charCodeAt(i) - base]--;
  }
  
  // 检查所有计数是否为 0
  return count.every(c => c === 0);
}

// 测试
console.log(isAnagram('anagram', 'nagaram')); // true
console.log(isAnagram('rat', 'car'));         // false

时间复杂度：O(n)，空间复杂度 O(1)（固定 26 个位置）。

关键点

• 字母异位词的本质：两个字符串包含相同的字符，且每个字符出现次数相同
• 排序法简单直观，但时间复杂度较高 O(n log n)
• 哈希表计数法时间复杂度 O(n)，是更优解
• 如果只包含小写字母，可用长度 26 的数组代替哈希表，空间更优
• 先判断长度可以快速排除不可能的情况