49. 字母异位词分组

解题过程

INFO

题目链接给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次

javascript

/**
 * @link https://leetcode.cn/problems/group-anagrams/
 * @title 49. 字母异位词分组
 * @description 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 * 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次
 * @param {string[]} strs
 * @return {string[][]}
 */
// 解法一
// 思路：通过数组存储判断相同匹配的字符串异位词，用于划分相同异位词分类
// 缺点：超出时间限制
var groupAnagrams = function (strs) {
  const res = []

  for (let i = 0; i < strs.length; i++) {
    if (res.length) {
      const target = res.findIndex(item => [...item[0]].sort().join('') === [...strs[i]].sort().join(''))
      if (target > -1) {
        res[target].push(strs[i])
      } else {
        res.push([strs[i]])
      }
    } else {
      res.push([strs[i]])
    }
  }

  return res
}

// 解法二
// 思路：针对解法一做了优化，但是没用
// 缺点：超出时间限制
var groupAnagrams = function (strs) {
  const res = []

  for (let i = 0; i < strs.length; i++) {
    if (res.length) {
      let target = false
      for (let j = 0; j < res.length; j++) {
        if ([...res[j][0]].sort().join('') === [...strs[i]].sort().join('')) {
          res[j].push(strs[i])
          target = true
          break
        }
      }

      !target && res.push([strs[i]])
    } else {
      res.push([strs[i]])
    }
  }

  return res
}

// 解法三
// 思路：针对解法二做的优化
// 缺点：超出时间限制
var groupAnagrams = function (strs) {
  const res = []
  const resMap = new Map()

  for (let i = 0; i < strs.length; i++) {
    if (res.length) {
      let target = false
      for (const key of resMap.keys()) {
        if (key === [...strs[i]].sort().join('')) {
          target = true
          res[resMap.get(key)].push(strs[i])
          break
        }
      }

      if (!target) {
        res.push([strs[i]])
        resMap.set([...strs[i]].sort().join(''), res.length - 1)
      }
    } else {
      resMap.set([...strs[i]].sort().join(''), 0)
      res.push([strs[i]])
    }
  }

  return res
}

// 解法四
// 思路：利用map存储相同哈希值的数组字符串
var groupAnagrams = function (strs) {
  const res = new Map()

  for (let i = 0; i < strs.length; i++) {
    const key = [...strs[i]].sort().join('')
    if (res.has(key)) {
      res.get(key).push(strs[i])
    } else {
      res.set(key, [strs[i]])
    }
  }

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

// 解法五
// 思路：用对象存储对应哈希值的键每次设置即可，跟解法四类似
// 缺点：执行结果比解法四稍差一点
var groupAnagrams = function (strs) {
  const res = {}

  for (let i = 0; i < strs.length; i++) {
    const key = [...strs[i]].sort().join('')
    if (res[key]) {
      res[key].push(strs[i])
    } else {
      res[key] = [strs[i]]
    }
  }

  return Object.values(res)
}

const result = groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]) // [["bat"],["nat","tan"],["ate","eat","tea"]]
// const result = groupAnagrams(['']) //[['']]
// const result = groupAnagrams(['a']) //[['a']]
console.log(result)

解题感受

前三种解法都走了弯路，暴力解法，但是结果超出了时间限制。第四五种解法类似，还是要使用哈希表解法才行

49. 字母异位词分组 ​

解题过程 ​

解题感受 ​

优质题解 ​

49. 字母异位词分组

解题过程

解题感受

优质题解