GuilinDev

Lc0049

05 August 2008

49 - Group Anagrams

原题概述

Given an array of strings, group anagrams together.

Example:

1
2
3
4
5
6
7

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.

题意和分析

给一个字符串数组，把所有的anagrams异构体归在一起，最后返回每个anagram的组，首先可以遍历整个个字符串数组，每遇到一个字符串就对其排序，如果同为anagrams排序后会是同样的字符串，依次字符串为key，以一个anagram下的 字符串列表为value，然后从hashmap中打印出所有的值即可；

改进的办法不用排序， 每个字母对应一个质数，将一个字符串中的字母对应的质数做乘法，异构体所得的乘积一定相同。

代码

HashMap + 排序的办法，时间复杂度O(NKlogK)，空间复杂度O(NK)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }

        HashMap<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] cha = s.toCharArray();
            Arrays.sort(cha);//对字符串转换的字符数组进行排序
            String keyStr = String.valueOf(cha);//字符数组转换成字符串的key
            if (!map.containsKey(keyStr)) {//第一次出现就新增一个key
                map.put(keyStr, new ArrayList<>());
            }
            map.get(keyStr).add(s);
        }
        return new ArrayList<>(map.values());//map.values()获得HashMap的所有的值
    }
}

在上面HashMap方法的基础上，不直接Arrays.sort()的结果当作key，而是自己生成key，时间复杂度O(NK)，空间复杂度O(NK)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    /**
    将HashMap的key用特殊的值来代替，把KlogK优化到K
    */
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) {
            return new ArrayList<>();
        }
        Map<String, List> map = new HashMap<>();
        int[] count = new int[26]; // 都是小写字母
        for (String str : strs) {
            Arrays.fill(count, 0); // 每个str重新default
            for (char c : str.toCharArray()) {
                count[c - 'a']++;
            }

            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {// 生成特殊的key
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString(); // 拿到unique的字符串key了
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(str);
        }
        return new ArrayList(map.values());
    }
}

HashMap + 质数做乘积找key，时间复杂度O(NK)，空间复杂度O(NK)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public static List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }

        // 用质数作为每个字母的唯一标识key，然后做乘法，异构体所的一定相同，最多10609个
        int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};

        HashMap<Integer, List<String>> map = new HashMap<>();
        for (String s : strs) {
            int key = 1;
            for (char c : s.toCharArray()) {//获得质数乘积做成的key，异构体的key一样
                key *= prime[c - 'a'];//找到prime中对应的质数
            }

            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}
This site is open source. Improve this page.