TNotes.leetcode

Appearance

0242. 有效的字母异位词【简单】

0242. 有效的字母异位词【简单】 ​

1. 📝 题目描述 ​

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

字母异位词

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

示例 1：

txt
输入: s = "anagram", t = "nagaram"
输出: true

示例 2：

txt
输入: s = "rat", t = "car"
输出: false

提示：

  • 1 <= s.length, t.length <= 5 * 10^4
  • s 和 t 仅包含小写字母

进阶：如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

题目分析

字母异位词是指两个字符串中的字符完全相同，只是字符的顺序不同。判断两个字符串是否为字母异位词的关键是：

  1. 两个字符串长度必须相等
  2. 每个字符出现的次数必须相同

2. 🎯 s.1 - 排序比较 ​

js
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  // 长度不同直接返回 false
  if (s.length !== t.length) return false

  // 对两个字符串排序后比较
  return s.split('').sort().join('') === t.split('').sort().join('')
}
  • 时间复杂度：O(nlog⁡n)，主要是排序的时间复杂度
  • 空间复杂度：O(n)，需要额外空间存储字符数组

3. 🎯 s.2 - 哈希表计数 ​

js
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  // 长度不同直接返回 false
  if (s.length !== t.length) return false

  // 使用对象记录字符出现次数
  const charCount = {}

  // 统计字符串 s 中每个字符的出现次数
  for (let i = 0; i < s.length; i++) {
    const char = s[i]
    charCount[char] = (charCount[char] || 0) + 1
  }

  // 遍历字符串 t，减少对应字符的计数
  for (let i = 0; i < t.length; i++) {
    const char = t[i]
    if (!charCount[char]) {
      return false
    }
    charCount[char]--
  }

  return true
}
  • 时间复杂度：O(n)，需要遍历两个字符串各一次
  • 空间复杂度：O(1)，最多存储 26 个字符的计数（假设只包含小写字母）

4. 🎯 s.3 - 数组计数（仅适用于小写字母） ​

js
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  // 长度不同直接返回 false
  if (s.length !== t.length) return false

  // 创建长度为 26 的数组，记录每个字母的出现次数
  const charCount = new Array(26).fill(0)

  // 统计字符出现次数差异
  for (let i = 0; i < s.length; i++) {
    charCount[s.charCodeAt(i) - 97]++ // s 中字符计数加 1
    charCount[t.charCodeAt(i) - 97]-- // t 中字符计数减 1
  }

  // 检查是否所有计数都为 0
  for (let i = 0; i < 26; i++) {
    if (charCount[i] !== 0) {
      return false
    }
  }

  return true
}
  • 时间复杂度：O(n)，需要遍历两个字符串各一次
  • 空间复杂度：O(1)，固定大小的数组

Discussions