LeetCode(Arrays&Strings)Group Anagrams

Group Anagrams

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

思路：想到通过对String转换成char [] 然后排序，如果两个字符串排序后的结果内容相等的话就说明这两个字符串的是Anagrams。代码如下：算法正确，但是运行超时了。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
	  List<List<String>> res=new ArrayList<>();
	        int len=strs.length;
	        if(len==0){
	            return res;
	        }
	        ArrayList<String> strslist=new ArrayList<String>(Arrays.asList(strs));
	        
	        for(int i=0;i<strslist.size();i++){
	            ArrayList<String> list=new ArrayList<String>();
	            list.add(strslist.get(i));
	            for(int j=0;j<strslist.size();j++){
	                if(j==i){
	                    continue;
	                }
	                char [] stri=strslist.get(i).toCharArray();
	                char [] strj=strslist.get(j).toCharArray();
	                Arrays.sort(stri);
	                Arrays.sort(strj);
	                if(Arrays.equals(stri, strj)){
	                    list.add(strslist.remove(j));
                        j--;
	                }
	            }
	            res.add(list);
	        }
	        return res;
    }
}

这种题目，里边有防止重复的计算量时候，考虑用map结构来回更加有效率，利用map后的代码如下，通过全部测试用例。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
	    List<List<String>> res=new ArrayList<>();
	        int len=strs.length;
	        if(len==0){
	            return res;
	        }
	        HashMap<String,List<String>> map=new HashMap<>();
         for(String s:strs){
             char [] arr=s.toCharArray();
             Arrays.sort(arr);
             String skey=String.valueOf(arr);
             if(!map.containsKey(skey)){
                 map.put(skey,new ArrayList<>());
             }
             map.get(skey).add(s);
         }
         
	     res.addAll(map.values());
	     return res;
    }
}