LeetCode：49. 字母异位词分组（中等）

问题链接

49. 字母异位词分组

问题描述

给你一个字符串数组，请你将 字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
提示：

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

示例

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

示例 2:
输入: strs = [""]
输出: [[""]]

示例 3:
输入: strs = ["a"]
输出: [["a"]]

解题思路

我们可以先将问题问题进行拆分:

1. 如果有两个字符串，如何判断他们是不是字母异位词
   字母异位词也就是说：单词对应的字母的集合是一样的。判断的方法也很多：
   a. 对字符串的字母进行排序，排序后比较两个字符串是否相同；
   b. 先遍历一个字符串中的字母，将字母和字母出现的次数存到一个map里面；然后再遍历另外一个字符串的字母，用map中找到之前存的次数并减1，如果出现找不到或者次数为负，则说明不是字母异位词；反之，则是。

2. 如何高效的进行分组
   如果采用“排序”的方法判断字母异位词，那么这里非常简单：
   我们将排序后的字符串作为key，对所有的字符串进行分组。

代码示例（JAVA）

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> result = new HashMap<>();

        for (int i = 0; i < strs.length; i++) {
            char[] arr = strs[i].toCharArray();
            Arrays.sort(arr);
            String str = new String(arr);
            if (result.get(str) == null) {
                List<String> list = new ArrayList<>();
                list.add(strs[i]);
                result.put(str, list);
            } else {
                result.get(str).add(strs[i]);
            }
        }
        
        return new ArrayList<>(result.values());
    }
}

执行结果