leetcode解题: Group Anagrams (49)

发表于 | 分类于

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"]
]

Note: All inputs will be in lower-case.

解法1：HashMap, O(N) Time + O(N) Space

因为anagram是表示排序后A,B的字母一样，那么就可以用一个hashmap存储每一个group， group的key就是排序后的string。
string排序在java中并没有自带的函数，可以先转换成chararray，然后用Arrays.sort来排序。
Java

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
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0) {
            return res;
        }
        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for (String str: strs) {
            String temp = sorted(str);
            if (!map.containsKey(temp)) {
                ArrayList<String> collection = new ArrayList<String>();
                collection.add(str);
                map.put(temp, collection);
            } else {
                map.get(temp).add(str);
            }
        }
        
        for (String key : map.keySet()) {
            res.add(map.get(key));
        }
        
        return res;
        
    }
    
    public String sorted(String x) {
        char[] temp = x.toCharArray();
        Arrays.sort(temp);
        return new String(temp);
    }
}