49. Group Anagrams_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"]
]

思路: 题目意思是将具有相同字母的单词放在一组里.由于有26个字母,可以以字母出现次数构成的字符串为键构建map,属于同一键的即是属于一个list.

时间复杂度:O(N*M) N为字符串个数.M为单个字符串的长度

空间复杂度:O(N)

<span style="font-size:14px;">public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result=new ArrayList<List<String>>();
        if(strs==null)
            return result;
        HashMap<String,List<String>> map=new HashMap<String,List<String>>();
        
       
        for(int i=0;i<strs.length;i++){
            StringBuilder sb=new StringBuilder("");
            int[] num=new int[26];
            for(int j=0;j<strs[i].length();j++){
                num[strs[i].charAt(j)-'a']++;
            }
            
            for(int j=0;j<26;j++)
                sb.append(num[j]);
            List<String> list=new ArrayList<String>();
            if(map.containsKey(sb.toString())){
                list=map.get(sb.toString());
                list.add(strs[i]);
                map.put(sb.toString(),list);
            }else{
                list.add(strs[i]);
                map.put(sb.toString(),list);
            }
         
        }
        for(String str:map.keySet()){
            result.add(map.get(str));
        }
        
        return result;
    }
}</span>