【算法题解】25. 字母异位词分组

这是一道 简单 题
https://leetcode.cn/problems/group-anagrams/description/

题目描述

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""] 
输出: [[""]] 

示例 3:

输入: strs = ["a"] 
输出: [["a"]]

提示：

• 1<=strs.length<=1041 <= strs.length <= 10^41<=strs.length<=104
• $0<=strs[i].length<=100$
• $strs[i]$ 仅包含小写字母

解题思路

将字符串排序，如果排序后的字符串是一样的就是字母异位词。

可以使用哈希表这类数据结构，key 存排序后的字符串，value 存排序后一样的原字符串列表。

逻辑非常简单，循环遍历给定字符串列表，并对每一个字符串排序，将排序结果和原字符串存放到哈希表中，具体实现看代码。

Java 代码实现

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> cache = new HashMap<String, List<String>>();for (String str : strs) {char[] ch = str.toCharArray();Arrays.sort(ch);String sorted = new String(ch);if(!cache.containsKey(sorted)){cache.put(sorted, new ArrayList<>());}cache.get(sorted).add(str);}return new ArrayList<List<String>>(cache.values());}
}

Go 代码实现

func groupAnagrams(strs []string) [][]string {cache := make(map[string][]string)for _, str := range strs {s := []byte(str)sort.Slice(s, func(i int, j int) bool {return s[i] < s[j]})sorted := string(s)cache[sorted] = append(cache[sorted], str)}ans := make([][]string, 0)for _, value := range cache {ans = append(ans, value)}return ans
}

复杂度分析

• 时间复杂度：$O(nk)$，n 为给定字符串数组的长度，k 为字符串排序的时间复杂度。
• 空间复杂度：$O(n)$, n为给定字符串数组的长度， 哈希表value总共存放有n个字符串。