检验易位构词算法

算法"/>

检验易位构词算法

不要以恶报恶。众人以为美的事，要留心去做。若是能行，总要尽力与众人和睦。 —(罗马书12:17-18)

什么是易位构词

以下介绍来自维基百科

易位构词游戏的英文词汇是 anagram，这个词来源于有“反向”或“再次”的含义的希腊语字根ana-和有“书写”、“写下”的意思的词根grahpein。易位构词是一类文字游戏（更准确地说是一类“词语游戏”），是将组成一个词或短句的字母重新排列顺序，原文中所有字母的每次出现都被使用一次，这样构造出另外一些新的词或短句。

通俗的讲易位构词，就是对原单词的字母进行重新排列从而构词一个新词，它满足：
1. 新词语的每个字母都是出自原词。
2. 新词语单词长度跟原单词长度一样。
3. 原单词的每个字母都在新单词里出现。
4. 单词默认都是小写
比如dog－->god就符合易位构词规则，而good—>god则不符合。

算法思路

观察新词跟旧词，有个特点单词中的字母都是成对出现的，结合之前的博文犀利的异或求解，那么我们可以将新旧单词当成一个整体，挨个对字母异或操纵，最终的结果为0，则认为符合易位构词。于是有了下面的算法：

private static boolean isAnagrams1(String str1, String str2) {if (str1 == null || str2 == null || (str1.length() != str2.length())) {return false;}String string = str1 + str2;int x = 0;for (int i = 0; i < string.length(); i++) {x ^= string.charAt(i);}return (x == 0) ? true : false;
}

看起来程序结构清晰明了，且时间复杂度O(n)。似乎很完美啊。

但这其中有个雷点，如果新单词是形如”bb”这样的词，旧单词形如”aa”，循环异或后结果为0，但明显此时不符合易位构词的要求。

重新想办法解决，易位构词只是字母的顺序不同，如果用一个数据桶，将新单词中相同字母放入同一个桶中，然后在遍历旧单词，遇到相同的字母，就去桶里将字母取出来。最后各个桶都为空，则说明新旧单词符合易位构词。
在详细想下一些细节：

• 需要多少个数据桶？
  a~z共有26个字母，因此只要26个数据桶就能保证单词中的每个字母都能找到对应的数据桶。a对应0号桶，b对应1号桶。。。z对应25号桶
• 桶需要做标记，根据标记我们就知道这个桶用来放哪个字母，更进一步，桶里只用放数据的个数即可，因为最后只关心桶是不是为空。这样桶可以用int[26]来实现，而放一个字母a就是对int[0]+1，取一个字母a就是对int[0]-1

java代码实现：

private static boolean isAnagrams2(String str1, String str2) {if (str1 == null || str2 == null || (str1.length() != str2.length())) {return false;}int[] buckets = new int[26];for (int i = 0; i < str2.length(); i++) {buckets[str1.charAt(i) - 'a']++;buckets[str2.charAt(i) - 'a']--;}for (int bucket : buckets) {if (bucket != 0) {return false;}}return true;}