leetcode 49 Group Anagrams
z
 2018-04-07 21:33:58  

Given an array of strings, group anagrams together.

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

1
2
3
4
5
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]
  • 对每一个String，转换成char[]，利用sort进行排序。
  • 利用给一个hashmap，对应出第i个String所在的组别。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs.length == 0) return null;
        List<List<String>> ans = new ArrayList<List<String>>();
        
        Map<String, Integer> m = new HashMap<String, Integer> ();
        
        int count = 0;
        for(String i : strs){
            char[] arrayString = i.toCharArray();
            Arrays.sort(arrayString);
            if(m.containsKey(String.valueOf(arrayString))){
                int index = m.get(String.valueOf(arrayString));
                List<String> t = ans.get(index);
                t.add(i);
                
                ans.remove(index);
                ans.add(index, t);
                
            }
            else{
                List<String> t = new ArrayList<String> ();
                t.add(i);
                ans.add(t);
                m.put(String.valueOf(String.valueOf(arrayString)),count);
                count++;
            }
            
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
   def groupAnagrams(self, strs):
       """
       :type strs: List[str]
       :rtype: List[List[str]]
       """
       dic = {}
       for i in strs:
           counter = str(sorted(i))
           if counter not in dic:
               dic[counter] = []
           dic[counter].append(i)
       ans = []
       for i in dic.keys():
           ans.append(dic[i])
       return ans