Comment on page

49.Group-Anagrams

49. 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.

代码

Approach 1: Categorize by Sorted String

Map => key: sort
Complexity Analysis
  • Time Complexity: O(_N_K_log_K), where N is the length of strs, and K is the maximum length of a string in strs. The outer loop has complexity O(_N) as we iterate through each string. Then, we sort each string in O(_K_log_K) time.
  • Space Complexity: O(_N_K), the total information content stored in ans.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
​
Map<String, List> ans = new HashMap<String, List>();
for (String s : strs) {
char[] chs = s.toCharArray();
Arrays.sort(chs);
String key = String.valueOf(chs);
if (!ans.containsKey(key)) {
ans.put(key, new ArrayList());
ans.get(key).add(s);
}
}
return new ArrayList(ans.values());
}
​
}
Approach #2 Categorie by Count
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
Map<String, List> ans = new HashMap<String, List>();
int[] count = new int[26];
for (String s : strs) {
Arrays.fill(count, 0);
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < 26; i++) {
sb.append('#');
sb.append(count[i]);
}
String key = sb.toString();
if (!ans.containsKey(key)) {
ans.put(key, new ArrayList());
ans.get(key).add(s);
}
}
​
return new ArrayList(ans.values());
}
}
Approach #3
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<List<String>>();
if (strs == null) return result;
​
Map<String, ArrayList<String>> multiMap = new HashMap<String, ArrayList<String>>();
for (String str : strs) {
char[] strChar = str.toCharArray();
Arrays.sort(strChar);
String strSorted = String.valueOf(strChar);
if (multiMap.containsKey(strSorted)) {
ArrayList<String> aList = multiMap.get(strSorted);
aList.add(str);
multiMap.put(strSorted, aList);
} else {
ArrayList<String> aList = new ArrayList<String>();
aList.add(str);
multiMap.put(strSorted, aList);
}
}
​
// add List group to result
Set<String> keySet = multiMap.keySet();
for (String key : keySet) {
ArrayList<String> aList = multiMap.get(key);
Collections.sort(aList);
result.add(aList);
}
​
return result;
}
}