一、题目描述：

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

原题链接 ? 242. 有效的字母异位词

示例 1:

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

示例 2:

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

说明: 你可以假设字符串只包含小写字母。

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

初始代码：

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
};

二、思路分析：

思路1：排序

1. 如果s和t的长度不相等，直接返回false。

2. 如果s和t是异位词，相当于两个字符串排序后相等。

3. 将s和t排序后进行比较，如果相等返回true，不等返回false。

思路2：哈希表

1. 如果s和t的长度不相等，直接返回false。

2. 创建长度为26的数组table，table里记录每个字母出现的频次。

3. 先遍历记录字符串 s 中字符出现的频次。

4. 然后遍历字符串 t，减去 table中对应的频次，如果出现 table[i]<0，则说明 t 包含一个不在 s 中的额外字符，返回 false即可。

三、完整代码：

思路1：

var isAnagram = function (s, t) {
  if (s.length !== t.length) {
    return false
  }
  s = s.split('').sort((n1, n2) => n1.charCodeAt() - n2.charCodeAt())
  t = t.split('').sort((n1, n2) => n1.charCodeAt() - n2.charCodeAt())
  if (s.join('') == t.join('')) {
    return true
  } else {
    return false
  }
}

复杂度分析

• 时间复杂度：

  排序的时间复杂度+比较字符串长度相等的复杂度即O(nlogn+n)=O(nlogn)

思路2：

var isAnagram = function (s, t) {
  if (s.length !== t.length) {
    return false
  }
  let start = 'a'.codePointAt(0)
  const table = new Array(26).fill(0)
  for (let i = 0; i < s.length; ++i) {
    table[s.codePointAt(i) - start]++
  }
  for (let i = 0; i < t.length; ++i) {
    table[t.codePointAt(i) - start]--
    if (table[t.codePointAt(i) - start] < 0) {
      return false
    }
  }
  return true
}

复杂度分析

• 时间复杂度：O(n)，n为s的长度
• 空间复杂度：O(m)，m为字符集的大小，此处m=26

四、总结：

——

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情