字母异位词分组

题目

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

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

示例 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] 仅包含小写字母

题解

题解一（暴力法）

public static List<List<String>> groupAnagrams(String[] strs) {
    if (strs == null || strs.length == 0) {
        return new ArrayList<>();
    }
    List<List<String>> results = new ArrayList<>();
    if (strs.length == 1) {
        results.add(Collections.singletonList(strs[0]));
        return results;
    }
    int start = 0;
    while (start < strs.length) {
        if (strs[start] == null) {
            start++;
            continue;
        }
        List<String> list = new ArrayList<>();
        list.add(strs[start]);
        String startStr = strs[start];

        char[] charArray = startStr.toCharArray();
        Arrays.sort(charArray);
        for (int i = start + 1; i < strs.length; i++) {
            if (strs[i] == null) {
                continue;
            }
            String endStr = strs[i];
            char[] endStrCharArray = endStr.toCharArray();
            Arrays.sort(endStrCharArray);
            if (Arrays.equals(charArray, endStrCharArray)) {
                list.add(endStr);
                strs[i] = null;
            }
        }
        strs[start] = null;
        results.add(list);
        start++;
    }
    return results;
}

会超时报错

解法二（HashMap）

public static List<List<String>> groupAnagrams2(String[] strs) {
    List<List<String>> results = new ArrayList<>();
    if (strs == null || strs.length == 0) {
        return new ArrayList<>();
    }
    if (strs.length == 1) {
        results.add(Collections.singletonList(strs[0]));
        return results;
    }
    HashMap<String, List<String>> hashMap = new HashMap<>();
    for (String str : strs) {
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        String sortStr = Arrays.toString(charArray);
        if (hashMap.containsKey(sortStr)) {
            List<String> strings = hashMap.get(sortStr);
            strings.add(str);
        }else {
            hashMap.put(sortStr, new ArrayList<>(Collections.singletonList(str)));
        }
    }
    return new ArrayList<>(hashMap.values());
}

解法三（HashMap优化）

public static List<List<String>> groupAnagrams(String[] strs) {
    HashMap<String, List<String>> hashMap = new HashMap<>();
    for (String str : strs) {
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        String sortStr = Arrays.toString(charArray);
        List<String> strings = hashMap.getOrDefault(sortStr, new ArrayList<>());
        strings.add(str);
        hashMap.put(sortStr, strings);
    }
    return new ArrayList<>(hashMap.values());
}