字母异位词分组

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

即字符串 'abc' 和 'cab' 是字母异位词

核心逻辑 - 字母异位词判定

abc和bca是字母异位词，异位词都是所有字母的重新排列，如果将两个字符串分别进行排序，二者是相等的 'abc'.sort() === 'bca'.sort()

/**
 * @description 判定两个字符串是否是字母异位词
 * 
*/
function isAnagrams (str1: string, str2: string): boolean {
  return str1.split('').sort().join('') === str2.split('').sort().join('')
}

常规思路 - 基于字符串排序比较实现

1. 构建Map，存储相同key对应的字母异位词
2. 遍历字符串数组，判定字母异位词

/**
 * @description 字母异位词分组
 * 
*/
function groupAnagrams(strs: string[]): string[][] {
  // 构建map
  const map = new Map<string, string[]>()

  // 遍历
  for (const s of strs) {
    // 将当前字符串进行排序
    const key = s.split('').sort().join('')
    // 判断当前是否已经有异位词
    const values = map.get(key) ?? []
    values.push(s)
    // 存储
    map.set(key, values)
  }

  return [
    ...map.values()
  ]
}

算法复杂度

时间复杂度： $O(mnlogn)$，其中$m$为字符串数组strs的长度，$nlogn$为字符串分割数组后，进行sort排序的时间复杂度

空间复杂度： $O(mn)$，其中$m$为字符串数组strs的长度，$n$为字符串的最大长度

升级思路 - 使用计数法判定字母异位词

如果两个字符串是字母异位词，说明在每个字符串中出现的字符数量都是一致的，如果能将字符串中每个字符出现的字数进行统计，则能判断出二者是否是字母异位词

// 使用数组，统计字符串中每个字符出现的次数
const count = new Array(26).fill(0) // 26个字母

for (const c of s) {
  // 每个字符都有unicode码，将对于字符a的偏移差值，确定每个字符的索引位置
  count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++
}

如字符串 abc 经过处理，得到数组 count1 = [1, 1, 1, 0, 0, .....]，字符串bca经过处理，得到数组 count2 = [1, 1, 1, 0, 0, ....]，当比较 count1.toString() === count2.toString()成立时，说明二者是字母异位词

/**
 * @description 使用计数法查找字母异位词
 * 
*/
function groupAnagrams(strs: string[]): string[][] {
  // 以数组形式存储每个字符串中各个字符出现的次数
  const map = new Map<string, string[]>()

  for (const s of strs) {
    // 计数
    const count: number[] = new Array(26).fill(0)

    for (const c of s) {
      // 计算相对于'a'的unicode差值
      count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++
    }

    // 将count以字符串形式拼接
    const key = count.toString()

    const values: string[] = map.get(key) ?? []
    values.push(s)

    map.set(key, values)
  }

  return [
    ...map.values()
  ]
}

时间复杂度： $O(mn)$，其中$m$为字符串数组strs的长度，$n$为单个字符串长度。

空间复杂度： $O(mn)$，其中$m$为字符串数组strs的长度，$n$为字符串的最大长度。