Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:
[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
Note: All inputs will be in lower-case.
弱菜解法(Time Limit Exceeded)：
这些anagrams的相同之处是，map到一个数组中的时候对应的位会相同。所以我扫描每个词，这个数组对应成一个数组模拟的map，作为HashMap的key。这有个问题，就是每次new的数组都是不一样的对象，不能用containsKey做O(1)查找，而需要用Iterator一个个的遍历key，然后用Arrays.equals来对比，徒增了O(n)的复杂度。目测复杂度是O(n2)。
贴一下：
public List<List<String>> groupAnagrams(String[] strs) {
Map<int[], List<String>> hashMap = new HashMap<>();
for (String s : strs) {
boolean addedToExist = false ;
int[] map = new int[26];
for (int i = 0; i < s.length(); i++) {
map[s.charAt(i) - 'a']++;
}
if (hashMap.isEmpty()) {
hashMap.put(map, new ArrayList<String>());
}
Iterator iter = hashMap.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
int[] key = (int[]) entry.getKey();
if (Arrays.equals(key, map)) {
List<String> list = hashMap.get(entry.getKey());
list.add(s);
addedToExist = true;
// hashMap.put(key, list);//这里是否不需要put，因为list是引用
}
}
if (!addedToExist){
List<String> list = new ArrayList<>();
list.add(s);
hashMap.put(map , list);
}
}
List<List<String>> res = new ArrayList<>();
Iterator iter = hashMap.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<int[], ArrayList<String>> entry = (Map.Entry<int[], ArrayList<String>>) iter.next();
List<String> list = entry.getValue();
res.add(list);
}
return res;
}
好的解法：
用string做
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0 ) return new ArrayList<>();
Map<String , List<String>> map = new HashMap<>();
for (String s : strs){
char [] c = s.toCharArray();
Arrays.sort(c);
String key = String.copyValueOf(c);
if (map.containsKey(key)){
map.get(key).add(s);
}else {
List<String> list = new ArrayList<>();
list.add(s);
map.put(key, list);
}
}
return new ArrayList<>(map.values());
}
这个解法用sort巧妙地用String来作为key了。但我又想，不同内存地址的String，containsKey能返回true吗。。查了一下，因为String的hashCode是按照字符的utf-16的编码值求和，所以hash相同；hashmap用hash作为key，containsKey就会返回true了。
还可以精简成：
if (!map.containsKey(key)){
map.put(key, new ArrayList<String>());
}
map.get(key).add(s);
另外，把所有value加进ArrayList不需要Iterator，直接用 return new ArrayList<>(map.values());就行。
