49. 字母异位词分组

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

示例 1:

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

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

• 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
• 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
• 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

---

题解： 如果两个字符串从小到大排序后相等，那么两个字符串就互为字母异位词，否则不是。

例如 aab,aba,baa 排序后都是 aab，所以 aab,aba,baa 互为字母异位词。

示例 1 是怎么算的？

输入 strs=[eat,tea,tan,ate,nat,bat]。

每个字符串各自排序，得到 aet,aet,ant,aet,ant,abt。

把排序后相同的字符串分到同一组：

排序后是 aet 的字符串，排序前是 eat,tea,ate。

排序后是 ant 的字符串，排序前是 tan,nat。

排序后是 abt 的字符串，排序前是 bat。

因此，示例 1 返回的二维列表中，包含三个列表，分别为

[eat,tea,ate]。

[tan,nat]。

[bat]。

三个列表的顺序随意。

算法

用哈希表分组，把排序后的字符串当作哈希表的 key，排序前的字符串加到对应的列表中（哈希表的 value）。

最后把哈希表的所有 value 加到一个列表中返回。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> m = new HashMap<>();
        for(String s : strs) {
            // 循环把每个单词重新排序
            char[] sortedS = s.toCharArray(); //把字符串 `s` **拆分成一个字符数组**，数组里的每个元素对应字符串的一个字符。
            Arrays.sort(sortedS); // 对数组进行排序
            // 排序后相同的字符串，保存到同一组中
            String key = new String(sortedS);
            // 1. 先判断key是否存在
            if (!m.containsKey(key)) {
                // 2. 不存在就新建一个空列表，存入map
                m.put(key, new ArrayList<>());
            }
            // 3. 拿到这个列表，添加当前字符串
            m.get(key).add(s);
        }
        // 哈希表的所有 value 就是分组结果
        return new ArrayList<>(m.values()); 
    }
}

‍