链接

Given an array of strings, group anagrams together. 同字母异位词anagrams 指字母相同，但排列不同的字符串。
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.


求解

方法一：排序数组分类

顺序不同, 所以可以考虑将所有词的字母按顺序排列, 从而快速分组

点击查看【bilibili】

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.HashMap;
  4. import java.util.List;
  5. class Solution {
  6.     public List<List<String>> groupAnagrams(String[] strs) {
  7.         HashMap<String, List<String>> map = new HashMap<String, List<String>>();
  8.         if (strs.length == 0) return new ArrayList();
  9.         for (String s : strs) {
  10.             char[] cur = s.toCharArray();
  11.             Arrays.sort(cur);   // 复杂度: KlogK
  12.             String key = String.valueOf(cur);
  13.             if (!map.containsKey(key)){
  14.                 map.put(key, new ArrayList<>());
  15.             }
  16.             map.get(key).add(s);
  17.         }
  18.         return new ArrayList<List<String>>(map.values());
  19.     }
  20. }

复杂度分析
时间复杂度：O(N KlogK)，其中 N是 strs 的长度，而 K 是 strs 中字符串的最大长度。当我们遍历每个字符串时，外部循环具有的复杂度为 O(N)。然后，我们在 O(KlogK) 的时间内对每个字符串排序。

空间复杂度：O(NK)，排序存储在 ans 中的全部信息内容。

方法二：按计数分类

当且仅当它们的字符计数（每个字符的出现次数）相同时，两个字符串是字母异位词。

我们可以将每个字符串 s 转换为字符数 count，由26个非负整数组成，表示a，b，c 的数量等。我们使用这些计数作为哈希映射的基础。

在 Java 中，我们的字符数 count 的散列化表示将是一个用 ＃ 字符分隔的字符串。 例如，abbccc 将表示为 ＃1＃2＃3＃0＃0＃0 ...＃0 ，其中总共有26个条目。
image.png

  1. class Solution {
  2.     public List<List<String>> groupAnagrams(String[] strs) {
  3.         if (strs.length == 0) return new ArrayList();
  4.         Map<String, List> ans = new HashMap<String, List>();
  5.         int[] count = new int[26];
  6.         for (String s : strs) {
  7.             Arrays.fill(count, 0);
  8.             for (char c : s.toCharArray()) count[c - 'a']++;
  10.             StringBuilder sb = new StringBuilder();
  11.             for (int i = 0; i < 26; i++) {
  12.                 sb.append('#');
  13.                 sb.append(count[i]);
  14.             }
  15.             String key = sb.toString();
  16.             if (!ans.containsKey(key)) ans.put(key, new ArrayList());
  17.             ans.get(key).add(s);
  18.         }
  19.         return new ArrayList(ans.values());
  20.     }
  21. }

复杂度分析

时间复杂度：O(NK)，其中 N 是 strs 的长度，而 K 是 strs 中字符串的最大长度。计算每个字符串的字符串大小是线性的，我们统计每个字符串。

空间复杂度：O(NK)，排序存储在 ans 中的全部信息内容。