242. 有效的字母异位词 🟩

题目

leetcode 简单

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:
输入: s = “rat”, t = “car”
输出: false

提示：

1 <= s.length, t.length <= 5 * 104
⚠️ s 和 t 仅包含小写字母

题解

方法：排序

时间复杂度：O(nlogn)

排序的时间复杂度为 O(nlogn)，比较两个字符串是否相等时间复杂度为 O(n)，因此总体时间复杂度为 O(nlogn+n)=O(nlogn)。
空间复杂度：O(logn)

排序需要 O(logn) 的空间复杂度。

var isAnagram = function(s, t) {
    return s.length == t.length && [...s].sort().join('') === [...t].sort().join('')
};

方法：Array

时间复杂度：O(N)

N 为字符串的长度。我们只同时遍历了 s 和 t 一次，最后遍历了一个常数长度 26 的数组。非常极致。
空间复杂度：O(1)

数组长度固定为 26，与字符串长度无关。

function isAnagram(s, t) {
  // 1. 长度不同，直接出局
  if (s.length !== t.length) {
    return false
  }

  // 2. 创建一个长度为 26 的数组，初始值为 0
  const count = new Array(26).fill(0)

  // a 的 ASCII 码是 97，用来做基准偏移量
  const base = 'a'.charCodeAt(0)

  // 3. 同时遍历 s 和 t （因为长度已经相等了，只需要一个循环）
  for (let i = 0; i < s.length; i++) {
    console.log('♻️ i', i, s[i], s.charCodeAt(i), t[i], t.charCodeAt(i))

    // s[i] 对应的字母增加
    count[s.charCodeAt(i) - base]++
    // t[i] 对应的字母减少
    count[t.charCodeAt(i) - base]--

    console.log('count:', count)
  }

  // 4. 检查数组中是否全为 0
  for (let i = 0; i < 26; i++) {
    if (count[i] !== 0) {
      return false
    }
  }

  return true
}

console.log('🌰', isAnagram('anagram', 'nagaram')) // true
console.log('------------')
console.log('🌰', isAnagram('rat', 'car')) // false

执行结果

♻️ i 0 a 97 n 110
count: [
  1, 0, 0, 0, 0,  0, 0, 0,
  0, 0, 0, 0, 0, -1, 0, 0,
  0, 0, 0, 0, 0,  0, 0, 0,
  0, 0
]
♻️ i 1 n 110 a 97
count: [
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0
]
♻️ i 2 a 97 g 103
count: [
  1, 0, 0, 0, 0, 0, -1, 0,
  0, 0, 0, 0, 0, 0,  0, 0,
  0, 0, 0, 0, 0, 0,  0, 0,
  0, 0
]
♻️ i 3 g 103 a 97
count: [
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0
]
♻️ i 4 r 114 r 114
count: [
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0
]
♻️ i 5 a 97 a 97
count: [
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0
]
♻️ i 6 m 109 m 109
count: [
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0
]
🌰 true
------------
♻️ i 0 r 114 c 99
count: [
  0, 0, -1, 0, 0, 0, 0, 0,
  0, 0,  0, 0, 0, 0, 0, 0,
  0, 1,  0, 0, 0, 0, 0, 0,
  0, 0
]
♻️ i 1 a 97 a 97
count: [
  0, 0, -1, 0, 0, 0, 0, 0,
  0, 0,  0, 0, 0, 0, 0, 0,
  0, 1,  0, 0, 0, 0, 0, 0,
  0, 0
]
♻️ i 2 t 116 r 114
count: [
  0, 0, -1, 0, 0, 0, 0, 0,
  0, 0,  0, 0, 0, 0, 0, 0,
  0, 0,  0, 1, 0, 0, 0, 0,
  0, 0
]
🌰 false

为什么用 Array 没用 Map

题目有一个极其关键的已知条件：“假设字符串只包含小写字母”。

正是这个条件，决定了用 Array 是降维打击 Map 的最优解。原因有以下三点：

1. 没有“哈希开销”，访问速度极快

Map 的底层：当你往 Map 里存一个键值对（比如 map.set('a', 1)）时，底层需要计算 'a' 的哈希值，处理潜在的哈希冲突，然后再分配内存去存。这个过程虽然在算法复杂度上算作 O(1)，但在实际 CPU 执行时，步骤非常繁琐。
Array 的底层：因为只有 26 个小写字母，它们的 ASCII 码是连续的（'a' 是 97，'z' 是 122）。我们可以直接用一个长度为 26 的数组，把字母映射到索引上（'a' -> 0，'z' -> 25）。直接通过索引 arr[0]++ 访问内存，没有任何哈希计算，这是极其纯粹的 O(1)，速度通常比 Map 快好几倍。

2. 内存占用极小且固定

Map 的开销：JS 中的 Map 是一个复杂的对象，为了维护键值对、哈希表结构、插入顺序的链表指针等，即使只存 26 个字母，也会占用相对较多的内存堆空间。
Array 的开销：一个长度为 26 的数字数组，在 JS 引擎（V8）底层会被高度优化为连续的 C++ 数组，内存开销微乎其微。

3. 完美的 O(1) 空间复杂度

由于数组长度死死定在 26，无论你输入的字符串是 10 个字符还是 10 万个字符，空间永远是这点大，这是绝对标准的 O(1) 空间复杂度。

本页目录