题目描述

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

样例

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

说明：

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

算法分析

• 1、由于字符串内部的字符是有大小关系的，可以对里面的字符进行排序，再组合成一个字符串，组合后的字符串作为一个标准，例如：eat，ate，tae共同的标准是aet
• 2、将所有字符串分别放进属于自己的标准单词的链表中，例如aet 存放 eat，ate，tae
• 3、将所有标准单词对应的链表进行输出

时间复杂度 $O(NLlogL)$

有$N$个单词，每个单词的长度是$L$，排序单词的复杂度是$LlogL$

Java 代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,List<String>> map = new HashMap<String,List<String>>();
        int n = strs.length;
        for(int i = 0;i < n;i ++)
        {
            char[] c = strs[i].toCharArray();
            Arrays.sort(c);
            String s = new String(c);
            if(!map.containsKey(s)) map.put(s,new ArrayList<String>());
            map.get(s).add(strs[i]);
        }
        List<List<String>> ans = new ArrayList<List<String>>();
        for(List<String> t : map.values())
        {
            ans.add(t);
        }
        return ans;
    }
}