今天晚上参加了摩根士丹利的宣讲会，结束以后有一个快速的现场笔试，3 道编程题。我觉得还是有点难度的，如果想要优化的话。当然 WillowTY 说都是傻*题。

这张图是笔试结束的时候我偷拍的，最后一问没有想明白，所以想要再想一想。

第 1 题没什么好说的，就是看两个单词用的字母的个数是不是一样的。

由于只有 26 个字母，所以开一个数组，统计 word1 和 word2 中每个单词出现的次数，看次数是不是相等。

对于 word1，做 count++，对于 word2，做 count--，最后只要所有的 count 都为 0，那就是 Anagram，任意一个 count 不是 0，就不是 Anagram。

boolean isAnagram(String word1, String word2) {
    int[] count = new int[26];
    for (int i = 0; i < word1.length(); i++) {
        int index = word1.charAt(i) - 'a';
        count[i]++;
    }
    for (int i = 0; i < word2.length(); i++) {
        int index = word2.charAt(i) - 'a';
        count[i]--;
    }
    for (int i = 0; i < count.length; i++) {
        if (count[i] != 0) {
            return false;
        }
    }
    return true;
}

第 2 题就是遍历 dictionary，对于某一个 item，如果和 word 互为 Anagram，那么就返回这个单词。

由于可以使用第 1 问的函数，那事情就很简单了。

String findAnagram(String word, List<String> dictionary) {
    for (String s : dictionary) {
        if (isAnagram(s, word)) {
            return s;
        }
    }
    return null;
}

最关键的是第 3 题，题目也明确说了，简单的做法是，分别遍历 words 和 dictionary，每一次都调用第 2 问的函数来计算，只是这样效率太低了。

由于我前 2 问陷入了思维盲区，所以这一问没有一下子想到最优的方案。

在继续之前，先说一下前两问还有什么做法。

有一种是 WillowTY 跟我说的。

他的做法是，将 word1 和 word2 的每一位按字典序排序，例如 bbdas 排序后就变成 abbds。那么，显然，如果 word1 和 word2 互为 Anagram，显然他们每一位字符重新排序后形成的单词应该是一样的。

由此，可以得到第 1 问的伪代码是：

boolean isAnagram(String word1, String word2) {
    char[] c1 = word1.toCharArray();
    char[] c2 = word2.toCharArray();
    Arrays.sort(c1);
    Arrays.sort(c2);
    String s1 = new String(c1);
    String s2 = new String(c2);
    return s1.equals(s2);
}

我们假设每个单词的平均长度为 $a$，那么，这样的复杂度就是 $O(a \log a)$。

而我之前的做法的复杂度是 $O(a)$。

第 2 问，如果在这种排序的思路下，还是对 dictionary 的每一个单词做内部排序，包括 word。

List<String> newDictionary = new List<>();
for (String s : dictionary) {
    char[] c = s.toCharArray();
    Arrays.sort(c);
    newDictionary.add(new String(c));
}
// word 排序类似

之后对 newDictionary 排序，还是按照字典序。

Collections.sort(newDictionary);

这样一来，问题就变成了，找 newWord 是不是在 newDictionary 里面。

for (String s : newDictionary)
    if (s.euqals(newWord))
        // return

当然，由于这里的 s 已经是排序后的了，所以势必还要加一个 Map，完成排序前后的映射。

for (String s : dictionary) {
    // ...
    String t = new String(c);
    map.put(t, s);
    newDictionary.add(t);
}

for (String t : newDictionary)
    if (t.euqals(newWord))
        return map.get(t);

运用到的数据结构复杂了，但是可以降低复杂度。

假设 dictionary 长度为 $m$，则对字典排序 $O(m \log m)$，之前说每个单词排序的时间是 $O(a \log a)$，所以，所有的排序时间是 $O(m a \log a + m \log m)$，最后查找的时间是线性的， $O(m)$。

比较两个字符串的复杂度不是 O(1) ，所以排序复杂度不是 O(mlogm)

2019-03-16 经 zerol 指出后修订

甚至，由于字典已经有序，甚至可以用二分查找进一步加速。不过由于排序花的时间太长了，所以只能优化常数了。

回过来看我之前的方法，$O(ma)$。

这时候再考虑第 3 问，我当时笔试的时候能想到的只有 2 个优化。

第一，不是取出一个 s in words 去看是不是有 t in dictionary 满足 t.equals(s)，而是取出一个 t in dictionary 去看是不是有 s in words 满足 t.equals(s)，在这个过程中，维护一个可以被删除的 words 列表，一旦某一个位置填充了，就立刻将这个 word 从 words 移除，这样就相当于没有被找到的单词会越来越少，仅仅优化了常数，复杂度不变。

第二，对字典和原始列表排序，有一个显然的事实是如果两个单词互为 Anagram，他们的长度一定相等，所以只需要比较长度相等的部分就可以了。

这里需要自定义一个 Comparator，在调用 Collections.sort() 的时候传入这个 new Comparator() {}，比较的标准是，谁更短，谁排前面。

遍历字典的时候维护一个 leftPointer 和 rightPointer，分别表示长度为 $x$ 的单词是在字典的哪个区域。

也是常数优化。

按照 Willow 的方法，一劳永逸地对 words 和 dictionary 按照第 2 问的方法排序。

排序之前用 HashMap 记录原始单词和调换过顺序的单词之间的一一映射。

对字典排序 $O(m \log m)$，之前说每个单词排序的时间是 $O(a \log a)$，所以，所有的排序时间是 $O(m a \log a + m \log m)$，类似地，假设 words 的长度是 $n$，那么，对单词表的排序时间是 $O(n a \log a + n \log n)​$。

然后遍历 words，去找是不是在字典中出现，如果出现，则返回其 Map 的值。

除去排序用的时间，查找的时间只是遍历 words 的时间，如果查找字典用的也是遍历，那么查找部分就是平方的复杂度，如果用的是有序列表的二分查找或者树形结构的查找，那么总的查找复杂度是线性的。

加上排序用的时间，其实能接受。

后来我在写这篇文章的时候，想到，其实 WillowTY 的这个方法有一定的小瑕疵。

假设字典中有 dog 和 god，由于他们排序以后都是 dgo，所以，当 dgo 去反向查 Map 的时候，输出的就是只有一个，而不会有另一个。当然题目本来就只要求输出一个，所以这个不算是 BUG。

但是当 WillowTY 说出哈希的时候，我突然有了一个大胆想法。

假设存在一个哈希函数 $f$，计算字符串的哈希值，$f$ 使得两个字符串的哈希值相等，当且仅当这两个字符串中出现的每个字母的数量相同的时候，$f$ 的值相等。例如，$f(dog)=f(god)=f(ogd)$。

显然这样一个函数存在，因为有一个 a[26]，对这个数组哈希

2019-03-16 经 zerol 指出后修订

假设存在这样一个函数，那么，只需要重写 equals() 方法为 return hashcode(this) == hashcode(that) 即可，即，只要两个单词的每个字母出现次数一样，那么他们的 hashcode() 和 euqals() 是一样的。

于是，只需要：

for (String word : words) {
    if (dictionary.contains(word))
        // do something
}

并且，假设我们把字典做成了一个 K-V 键值对，键是字典中的每一个元素，值是键本身，那么，其实上面的代码就被简化成：

for (String word : words) {
    return dictionaryMap.get(word);
}

这里的含义就是，如果 dictionaryMap 有 word，由于重写了 hashcode() 和 equals()，所以说明字典中有一个单词和给定单词有着相同的字母数量，即互为 Anagram，所以直接返回 dictionaryMap.get(word)，而如果没有匹配的，那么 get() 本来返回的就是 null。

当然，这样一个哈希函数可能很难找，这是硬伤，决定了这个方法能不能用。

假设存在的话，就是这么简单。

况且，即便找到，也不建议重写 String 类的 hashcode() 和 euqals()，风险有点大。

仓促之间，感觉这次笔试非常不尽如人意，匆匆忙忙想好，然后写下来，很多细节都没有考虑到，所以有预感要凉凉。

这 3 道题肯定还有更好的方法，欢迎你留言与我探讨。