字母异位词分组

字母异位词分组（Group Anagrams）是另一个常见的算法问题，题目要求将给定的字符串数组中所有字母异位词（即由相同字母组成但排列不同的字符串）分组并返回。下面是用Java实现的解决方案：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建一个HashMap，用于存储字母异位词分组
        HashMap<String, List<String>> map = new HashMap<>();

        // 遍历字符串数组
        for (String str : strs) {
            // 将字符串转换为字符数组并进行排序
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);

            // 如果排序后的字符串已经存在于HashMap中，则将当前字符串添加到对应的分组中
            if (map.containsKey(sortedStr)) {
                map.get(sortedStr).add(str);
            } else {
                // 否则，创建一个新的分组，并将当前字符串添加到该分组中
                List<String> newList = new ArrayList<>();
                newList.add(str);
                map.put(sortedStr, newList);
            }
        }

        // 将所有分组添加到结果列表中
        List<List<String>> result = new ArrayList<>(map.values());

        return result;
    }
}

解释每一步：

1. 我们首先创建一个HashMap来存储字母异位词分组，其中键为字母重新排列后的字符串，值为对应的分组（字符串列表）。

2. 遍历给定的字符串数组。

3. 对于每个字符串，我们将其转换为字符数组并对字符数组进行排序，这样可以确保相同字母异位词经过排序后得到的字符串是相同的。

4. 如果排序后的字符串已经存在于HashMap中，则将当前字符串添加到对应的分组中。

5. 否则，创建一个新的分组，并将当前字符串添加到该分组中。

6. 最后，将HashMap中所有的分组添加到结果列表中，并返回结果列表。

这种解法的时间复杂度为O(n * k * log(k))，其中n为字符串数组的长度，k为字符串的平均长度。在这个解法中，最耗时的操作是对每个字符串排序。空间复杂度为O(n * k)，因为需要使用HashMap来存储分组，其中键的数量最多为n，每个分组的平均大小为k。