力扣49-字母异位词分组（中等）

题目描述

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

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

方法一：排序

思路

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

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            String sortStr = strSort(str);
            if (map.containsKey(sortStr)) {
                map.get(sortStr).add(str);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(sortStr, list);
            }
        }

        List<List<String>> result = new ArrayList<>();
        Set<String> sortStrKeys = map.keySet();
        for (String sortStrKey : sortStrKeys) {
            List<String> list = map.get(sortStrKey);
            result.add(list);
        }
        return result;
    }
	
    // 对字符串进行排序，使用Arrays.sort工具直接排序
    public String strSort(String string) {
        char[] chars = string.toCharArray();
        Arrays.sort(chars);
        // String string1 = chars.toString();
        String string1 = new String(chars);
        return string1;
    }
}

复杂度分析

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

空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。