题目

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

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

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

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

解答

解法一： 用Map<Integer, Integer>作为Map的key

想到可以将单词的每个字母作为一个数字（char – ‘a’），将其作为key保存在哈希表中，对应value是每个字母的个数，从而得到每个单词的哈希表。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<Map<Integer, Integer>, List<String>> map = new HashMap<>();
        for (String str : strs) {
            Map<Integer, Integer> charMap = new HashMap();
            char[] charArray = str.toCharArray();
            // 创建这个单词的charMap作为key
            for (char c : charArray) {
                Integer key = c - 'a';
                if (charMap.containsKey(key)) {
                    charMap.put(key, charMap.get(key) + 1);
                    continue;
                }
                charMap.put(key, 1);
            }
            if (map.containsKey(charMap)) {
                map.get(charMap).add(str);
                continue;
            }
            List<String> valueList = new ArrayList<>();
            valueList.add(str);
            map.put(charMap, valueList);
        }
        return new ArrayList(map.values();
    }
}

改进

把这个保存字母信息的Map用List<Integer>代替

解法2 字母重排序

想到可以将单词的每个字母作为一个数字（char – ‘a’），每次将key乘100加上这个数字，最终得到哈希表里的key。但是字母顺序不同的话，这个key不能匹配到，因此应该将字母中的字符先排序一次，就可以所有字母异位词对应一个key了。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String key = String.valueOf(charArray);
            List<String> list = new ArrayList<>();
            if (map.containsKey(key)) {
                list = map.get(key);
            }
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList(map.values());
    }
}

小结 & 注意点

• String有一个方法toCharArray()，用于将String转化为char[]；
• valueOf() 是String类的静态工厂方法