前几天参加某公司的面试，被问了这么一个问题：
有一个字符串组叫a， a = [a, abc, apple, …, zoo]。 其中像stop post tops 这样的就叫做同位词。
这么看来同位词也就是组成相同，长短一样的两个字符串。
我事后查了一下，这个题是编程珠玑上的一道题目，书上给出的方案是这样的。
先将字符串内部按顺序排列，比如bac->abc，然后字符串间在排序，就可以找到同位词。
我当时给出的答案却是这样的：
对a，b，c～z进行加权，让a=1，b=2，c=4～z=2^25，然后每个字符串就可以算出来唯一的特征值。
后来给面试官解释这个原理的时候说的不是很好，于是自己后来想了一下，觉得这个思路还是可以发展一下的。
###为什么要这么定权值？
对于2^n的这个序列，很明显相邻两个数之间的差值为2^x，x为相邻两个数之间的较小值。
假设存在一个式子：
2^a+2^b=2^c+2^d 其中a，b，c，d互不相等。
这里让a>d,c>b，对这个式子做一个变化。
2^a-2^d=2^c-2^b
由刚才的推论我们知道，等号左边或者右边的结果，一定至少是2^x这个格式，或者是2^x1+2^x2……。
式中x取式中较小值，这里让x分别取d和b。得到
2^d=2^b
这明显与假设不符（就算让他们展开为x1+x2这种也不符），因此可以得到一个结论。
在2^n的序列中，不存在 2^a+2^b=2^c+2^d。
也就是说，我将a，b，c赋2^n的权值，不会存在a+b=c的情况，也不会存在a+b=c+d的情况，这对于我们标记一个独特的字符串十分有用。
当然你可能会说a+a=b，但是计算权值是有前提的，就是字符串要等长，这样这个问题就可以规避掉了。
###当然这个方法也是有问题的！！ 细心的你估计马上就发现了，英文字母有26个，那么光计算z的权值就要2^25= 33554432 ，略大啊……如果有一个字符串是“zzzzzzz”，那还能不能愉快的计算了……
为了减少计算压力，我有这么几个方案：
-
将字母表中的前八位改为2^-8～2^0，计算的时候，先把小数点后提取出来，同时计算小数点后的权值和整数部分权值。
至于为啥是前八位，因为2^-8=0.00390625，小数点后已经有八位了……你看之前2的25次方也才八位数而已，当然这个方案也只是一个试想……
-
其实2^n不就是指一个二进制数么！
比如abc，按照之前的方案，其实就是111，ac就是101，这个值也是唯一的，那么我们完全可以把所有的字符串改为存储这样的数字啊！
比如有abc和bca，他们的权都是111，两者and一下，如果是1，那就是同位词，如果不是那妥妥的就不是了。当然这个法子的前提依旧是等长，不然的话aaac就等于abc了……
仔细的想了一下，编程珠玑上用来给每个字符串求特征序列，在进行排序的思路和我的思路本质上是一样的！
因为究其根本，还是把一个乱序转化为一个特征，只不过它需要先内部排序，再外部比较，我的方案在内部排序的时候速度更快一些，一轮循环就可以结束。在空间占用上，两个方案差不多。
今天分享了一个好玩的题目，我感觉是蛮有意思的，也感谢你的阅读。