49. 字母异位词分组

1. 题目

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

2. 思路

  • 由提示可知该题目仅包含小写字母，因此初始化map哈希数组用于存储每个字母出现的次数
  • 题目的直观意思其实是想将出现字母次数相同的字符串都收集到一起，其中不考虑字母顺序，这类字符串称为字母异位词
  • 解题的关键思路是如何将这一类字母出现次数一样的字符串收集起来，又得益于题目仅包含小写字母，因此可以在外扩展出一个哈希表，键为按顺序字母 + 其出现的频率次数组成的字符串，值则是对应的字符串数组
  • 初始化map哈希表用于收集字母异构词组
  • 循环计算出每个字符串的键，键由按顺序的字母 + 字母出现频率次数拼接组成，将字符串依次放入哈希表中
  • 完成收集后，可直接通过Map的values方法直接提取结果作为返回值

3. 代码

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
31
32
33
34
35
36
37
38
39
40
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        var map = new HashMap<String, List<String>>();

        for (var str : strs) {
            var mapString = getMapString(str);
            var list = map.getOrDefault(mapString, new ArrayList<String>());
            list.add(str);
            map.put(mapString, list);
        }

        return new ArrayList<List<String>>(map.values());
    }

    private String getMapString(String str) {
        var chArr = str.toCharArray();
        var map = new int[26];

        for (char ch : chArr) {
            map[getIndex(ch)]++;
        }

        var mapString = new StringBuilder();
        for (var i = 0; i < map.length; ++i) {
            if (map[i] != 0) {
                mapString.append(getChar(i)).append(map[i]);
            }
        }

        return mapString.toString();
    }

    private int getIndex(char ch) {
        return ch - 'a';
    }

    private char getChar(int index) {
        return (char)('a' + index);
    }
}

4. 复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

image-20230829184949087