满月的宝宝只有趴着才肯入睡# NextGeneration - 我爱宝宝
e*s
1 楼
Given an array of strings, return all groups of strings that are anagrams.
All inputs will be in lower-case
Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].
Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].
9章的参考程序如下, 他给每一个string换成26长度的int array. 然后用这个array生
成一个hash code. 问题是这个hashcode能够唯一对应一个anagram么. 不同的anagram
有没有对应同一个hashcode的可能 (考虑int overflow的情况下).
public class Solution {
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 ArrayList anagrams(String[] strs) {
ArrayList result = new ArrayList();
HashMap> map = new HashMap>();
for (String str : strs) {
int[] count = new int[26];
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i) - 'a']++;
}
int hash = getHash(count);
if (!map.containsKey(hash)) {
map.put(hash, new ArrayList());
}
map.get(hash).add(str);
}
for (ArrayList tmp : map.values()) {
if (tmp.size() > 1) {
result.addAll(tmp);
}
}
return result;
}
}
All inputs will be in lower-case
Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].
Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].
9章的参考程序如下, 他给每一个string换成26长度的int array. 然后用这个array生
成一个hash code. 问题是这个hashcode能够唯一对应一个anagram么. 不同的anagram
有没有对应同一个hashcode的可能 (考虑int overflow的情况下).
public class Solution {
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 ArrayList
ArrayList
HashMap
for (String str : strs) {
int[] count = new int[26];
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i) - 'a']++;
}
int hash = getHash(count);
if (!map.containsKey(hash)) {
map.put(hash, new ArrayList
}
map.get(hash).add(str);
}
for (ArrayList
if (tmp.size() > 1) {
result.addAll(tmp);
}
}
return result;
}
}
