49. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], 
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

要用Java写的话，就是在考Java方法的熟练度。用Map来降低二次查找的复杂度，Hash原理。把每个字符串排好序，相同放一个ArrayList，不同则新开一个，Map把排序好的和每个ArrayList对应，最后ans把Map的所有Values(ArrayList)添加进去即可。

但是看到leetcode官方的题解，发现煞笔了，直接return new ArrayList(mp.values());就可以了，利用ArrayList的构造函数，所以这题很考API的运用。

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
//        List<List<String>> ans = new ArrayList<>();
        //lc里面一定要判断这个
        if (strs.length == 0)
            return new ArrayList();
        Map<String, List<String>> mp = new HashMap<String, List<String>>();
        
        for(int i = 0; i < strs.length; i++) {
            char tmpArray[] = strs[i].toCharArray();
            //把字符排序
            Arrays.sort(tmpArray);
            String SortString = String.valueOf(tmpArray);
//            String tmpString = new String(tmpArray);
            
            if(mp.containsKey(SortString)) {
                mp.get(SortString).add(strs[i]);
            }
            else {
                List<String>tmpList = new ArrayList<String>();
                tmpList.add(strs[i]);
                mp.put(SortString, tmpList);
            }
        }
        
        //获取所有的mp映射值动态数组
//        Iterator iter = mp.values().iterator();
//        while(iter.hasNext()) {
//            List<String> tmpList = new ArrayList<String>((ArrayList<String>)iter.next());
//            ans.add(tmpList);
//        }
        return new ArrayList(mp.values());
    }
}

public class Main {

    
    public static void main(String[] args) {
        Solution s  = new Solution();
        String[] ss = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(s.groupAnagrams(ss));
    }

}

时间复杂度的分析:

 外层加上排序的，这里Sort是默认为快排的平均时间复杂度了。

还有一个更秒的方法，也稍微比这个优了一点，详见：https://leetcode.com/problems/group-anagrams/solution/