e*******s
发帖数: 1979 | 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
ArrayList>();
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;
}
} | Y****n
发帖数: 7 | 2 代码看着有点奇怪，既然已经设置了int[] count, 每次将str的每一个字母放进去之后
，然后从0到26依次搜集这些字母，遍组成了一个hash code，这样互为anagram的两个
字符串将拥有相同的hash code. 上面求解hash的 a *= b 存在溢出的风险。 | e*******s
发帖数: 1979 | 3 我也觉得 理论上是不能保证的溢出了还能保证unique.
一个26长度的int数组有INT_MAX^26种组合方式
远远超出int的范围.
就算每个int的范围是0~2 3^26也超出int的范围了.
我发现他们家贴的好多答案都简单粗暴的不负责任啊.
【在 Y****n 的大作中提到】
: 代码看着有点奇怪，既然已经设置了int[] count, 每次将str的每一个字母放进去之后
: ，然后从0到26依次搜集这些字母，遍组成了一个hash code，这样互为anagram的两个
: 字符串将拥有相同的hash code. 上面求解hash的 a *= b 存在溢出的风险。
|
|
