描述

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

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

示例

示例1：

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

示例2：

  1. 输入: strs = [""]
  2. 输出: [[""]]

示例3：

  1. 输入: strs = ["a"]
  2. 输出: [["a"]]

提示

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

解题思路

排序
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键，哈希表的值为一组字母异位词列表。

代码

  1. class Solution {
  2.     public List<List<String>> groupAnagrams(String[] strs) {
  3.         Map<String, List<String>> map = new HashMap<String, List<String>>();
  4.         for (String str : strs) {
  5.             char[] array = str.toCharArray();
  6.             Arrays.sort(array);
  7.             String key = new String(array);
  8.             List<String> list = map.getOrDefault(key, new ArrayList<String>());
  9.             list.add(str);
  10.             map.put(key, list);
  11.         }
  12.         return new ArrayList<List<String>>(map.values());
  13.     }
  14. }

复杂度分析

  • 时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量 k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(nklogk)。
  • 空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。