在美版leetcode上看到大神的思路,用质数表示26个字母,把字符串的各个字母相乘,这样可保证字母异位词的乘积必定是相等的。其余步骤就是用map存储,和别人的一致了。(这个用质数表示真的很骚啊!!!)
//因为找不到一个可以比对的代号 因为String值相同 地址可能不同 所以苦于这个方法 发现leetcode真是的人才多 用质数乘出来的数去保存 牛逼
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length ==0) return new ArrayList<List<String>>(); //效率提高30% 看来里面坑多
List<List<String>> arrll = new LinkedList<List<String>>();
HashMap<Long, List<String>> hsm = new HashMap<Long, List<String>>();
for (int i = 0; i < strs.length; i++) {
long s = find(strs[i]);
if (!hsm.containsKey(s)) {
List<String> arrstr = new LinkedList<String>();
arrstr.add(strs[i]);
hsm.put(s, arrstr);
} else {
hsm.get(s).add(strs[i]);
}
}
arrll.addAll(hsm.values());
return arrll;
}
public long find(String temp) {
int arr[] = {2,5,7,11,13 ,17,19,23,29,31 ,37,41,43,47,53, 59,61,67,71,73, 79,83,89,97,101,103};
long ans = 1 ;
for(int i = 0 ; i< temp.length();i++) {
ans *= arr[(temp.charAt(i)-'a')];
}
return ans;
}
}