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
     
      
       > groupAnagrams(String[] strs) {//        List
       
        
         > ans = new ArrayList<>();        //lc里面一定要判断这个        if (strs.length == 0)            return new ArrayList();        Map
         
          > mp = new HashMap
          
           >(); 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
           
            tmpList = new ArrayList
            
             (); tmpList.add(strs[i]); mp.put(SortString, tmpList); } } //获取所有的mp映射值动态数组// Iterator iter = mp.values().iterator();// while(iter.hasNext()) {// List
             
               tmpList = new ArrayList
              
               ((ArrayList
               
                )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/