前几天参加某公司的面试,被问了这么一个问题:

有一个字符串组叫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”,那还能不能愉快的计算了……

为了减少计算压力,我有这么几个方案:

  1. 将字母表中的前八位改为2^-8~2^0,计算的时候,先把小数点后提取出来,同时计算小数点后的权值和整数部分权值。

    至于为啥是前八位,因为2^-8=0.00390625,小数点后已经有八位了……你看之前2的25次方也才八位数而已,当然这个方案也只是一个试想……

  2. 其实2^n不就是指一个二进制数么!

    比如abc,按照之前的方案,其实就是111,ac就是101,这个值也是唯一的,那么我们完全可以把所有的字符串改为存储这样的数字啊!

    比如有abc和bca,他们的权都是111,两者and一下,如果是1,那就是同位词,如果不是那妥妥的就不是了。当然这个法子的前提依旧是等长,不然的话aaac就等于abc了……

仔细的想了一下,编程珠玑上用来给每个字符串求特征序列,在进行排序的思路和我的思路本质上是一样的!

因为究其根本,还是把一个乱序转化为一个特征,只不过它需要先内部排序,再外部比较,我的方案在内部排序的时候速度更快一些,一轮循环就可以结束。在空间占用上,两个方案差不多。

今天分享了一个好玩的题目,我感觉是蛮有意思的,也感谢你的阅读。