LeetCode-49-字母异位词分组

题目

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

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

示例 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] 仅包含小写字母

题解

思路其实还是比较清晰的：

理所当然我们需要判断哪些单词是字母异位词？其实是统计字母出现次数相同，但是这里我们使用排序的方法，排序后相同的单词一定是字母异位词。

那么接下来只需要遍历strs数组，然后对每个单词都进行排序，使用一个map保存排序后的string-在res里的下标，判断排序后的单词是否是新单词（不是之前某个单词的字母异位词），新单词我们就做新的插入操作；否则就放到相应的字母异位词里去就可以了。时间复杂度97.86%嘿嘿(●ˇ∀ˇ●)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 需要判断哪些单词是字母异位词
        // 遍历strs数组，对每个字符串进行排序，然后判断是否是字母异位词（排序后看是否相等）
        // 是就加入到res对应位置，不是就当作新的加入
        List<List<String>> res = new ArrayList<>();
        // map保存的键值对为 排序后的string - 和在res里的下标
        HashMap<String, Integer> map = new HashMap<>();

        for (int i = 0; i < strs.length; i++) {
            char[] charArray = strs[i].toCharArray();
            Arrays.sort(charArray);
            String stringSort = new String(charArray);

            // 如果相等了，说明是字母异位词
            if (map.get(stringSort) != null) {
                res.get(map.get(stringSort)).add(strs[i]);
            } else {
                // 不相等作为新的加入
                map.put(stringSort, res.size());
                List<String> listTemp = new ArrayList<>();
                listTemp.add(strs[i]);
                res.add(listTemp);
            }
        }

        return res;
    }
}