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.
Solution: 3种方法:1.把string变为char array后sort了再变为string,再放进hashmap;2.统计string出现字符的种数和个数,计算hash值;3.每个字符对应一个质数,相乘得到hash值
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> ans = new ArrayList<List<String>>();
if(strs == null || strs.length == 0){
return ans;
}
HashMap<Integer, ArrayList<Integer>> hashmap = new HashMap<Integer, ArrayList<Integer>>();
//solution1: sort char array
// for(int i = 0; i < strs.length; i++){
// char[] chars = strs[i].toCharArray();
// Arrays.sort(chars);
// String arranged = new String(chars);
// if(!hashmap.containsKey(arranged)){
// ArrayList<Integer> list = new ArrayList<Integer>();
// list.add(i);
// hashmap.put(arranged, list);
// } else{
// hashmap.get(arranged).add(i);
// }
// }
for(int i = 0; i < strs.length; i++){
int[] count = new int[26];
for(int j = 0; j < strs[i].length(); j++){
count[strs[i].charAt(j) - 'a']++;
}
int hash = getHash(count);
if(!hashmap.containsKey(hash)){
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(i);
hashmap.put(hash, list);
} else{
hashmap.get(hash).add(i);
}
}
for(Map.Entry<Integer, ArrayList<Integer>> entry : hashmap.entrySet()){
List<String> anagrams = new ArrayList<String>();
for(Integer i : entry.getValue()){
anagrams.add(strs[i]);
}
ans.add(anagrams);
}
return ans;
}
private int getHash(int[] count) {
int hash = 0;
int a = 378551;
int b = 63689;
for (int num : count) {
hash = hash * a + num;
a = a * b;
}
return hash;
}
利用对应质数:
public static List<List<String>> groupAnagrams(String[] strs) {
int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};//最多10609个z
List<List<String>> res = new ArrayList<>();
HashMap<Integer, Integer> map = new HashMap<>();
for (String s : strs) {
int key = 1;
for (char c : s.toCharArray()) {
key *= prime[c - 'a'];
}
List<String> t;
if (map.containsKey(key)) {
t = res.get(map.get(key));
} else {
t = new ArrayList<>();
res.add(t);
map.put(key, res.size() - 1);
}
t.add(s);
}
return res;
}