#有效的字母异位词

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: (s = 'anagram'), (t = 'nagaram')

输出: true 示例 2:

输入: (s = 'rat'), (t = 'car')
输出: false

提示:

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

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

#解题思路

题目信息：小写字母

#思路一

哈希表，两个字符串分别生成哈希表，以 a 开始的 ascii 码减去 a 的 ascii 码作为 key，对字母数量进行统计，统计后遍历两个哈希表进行比较，完全相同则是，复杂度 O(n)

进阶暂未考虑

#首次代码

function isAnagram(s: string, t: string): boolean {
  const sHash = {}
  const tHash = {}

  s.split('').forEach((i) => {
    const key = i.charCodeAt(0) - 'a'.charCodeAt(0)
    typeof sHash[key] !== 'number' ? (sHash[key] = 1) : sHash[key]++
  })

  t.split('').forEach((i) => {
    const key = i.charCodeAt(0) - 'a'.charCodeAt(0)
    typeof tHash[key] !== 'number' ? (tHash[key] = 1) : tHash[key]++
  })

  return Object.entries(s.length > t.length ? sHash : tHash).every(
    ([key, value]) => (s.length > t.length ? tHash : sHash)[key] === value,
  )
}

#优化代码

不需要生成两个哈希表，第二个字符串遍历时在第一个哈希表上做减法，最后遍历哈希表查看是否有非零数就可以了，复杂度 O(n)

function isAnagram(s: string, t: string): boolean {
  const hash = {}

  s.split('').forEach((i) => {
    const key = i.charCodeAt(0) - 'a'.charCodeAt(0)
    typeof hash[key] !== 'number' ? (hash[key] = 1) : hash[key]++
  })

  t.split('').forEach((i) => {
    const key = i.charCodeAt(0) - 'a'.charCodeAt(0)
    typeof hash[key] !== 'number' ? (hash[key] = -1) : hash[key]--
  })

  return !Object.values(hash).some((value) => value !== 0)
}

#复习结果

function isAnagram(s: string, t: string): boolean {
  const letter2countLongMap: Record<string, number> = {}

  let long = ''
  let short = ''
  if (t.length > s.length) {
    long = t
    short = s
  } else {
    long = s
    short = t
  }

  for (let i = 0; i < long.length; i++) {
    if (typeof letter2countLongMap[long[i]] === 'number') {
      letter2countLongMap[long[i]]++
    } else {
      letter2countLongMap[long[i]] = 1
    }
  }

  for (let i = 0; i < short.length; i++) {
    if (typeof letter2countLongMap[short[i]] === 'number') {
      letter2countLongMap[short[i]]--
    } else {
      return false
    }
  }

  return !Object.values(letter2countLongMap).some((i) => i > 0)
}

#进阶优化

字符串 unicode 排序后如果是异位词则相同，复杂度 O(nlogn)

function isAnagram(s: string, t: string): boolean {
  return strSort(s) === strSort(t)
}

function strSort(s: string) {
  return s.split('').sort().join('')
}