LeetCode/49. 字母异位词分组

49. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例 :

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

说明：

• 所有输入均为小写字母。
• 不考虑答案输出的顺序。

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

按照题目的要求，只有字母出现次数完全相同的两个组合，才可以被称为异位词，针对这一点，有两种思路，第一种就是，先对字符进行排序，将排序后的字符数组作为Key，当前字符串作为Value存入一个Map当中，最后返回Map集合中的Values即可；第二种思路是，由于字母出现次数相同，我们可以把每一位字符加起来，其和作为Key，当前字符串为Value，后续操作和第一种思路相同。当前，官方给出的第二种计数思路其实都大同小异，读者可以自行参考。

具体代码如下：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0)
            return new ArrayList<>();
        //创建一个Map用于临时存放结果
        Map<String, List<String>> map = new HashMap<>();
        //遍历每一个字符串
        for (String str : strs) {
            List<String> list;
            char[] temp = str.toCharArray();
            //对当前字符串中的字母排序
            Arrays.sort(temp);
            //将排序后的字符数组转换成String用作Map的Key
            String s = new String(temp);
            
			//在Map中查找异位词，如果有取出结果并将当前满足条件的str加入到Map中
            //如果不存在则新建一个List
            list = map.getOrDefault(s, new ArrayList<>());
            list.add(str);
            map.put(s, list);
        }
        return new ArrayList<>(map.values());
    }
}