Baidu某面试题＋解答

问题：给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。  （这道题面试官说有O(1) 的解法，。。。。。）

 

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

解答1：

定义 操作 F(A1,A2,A3....An)=P(A1)*P(A2)*P(A3).....P(An);

其中 P(A1)= PrimeNum[A1-'a'],
    PrimeNum 是从2开始的连续 素数 数组(2,3,5,7,.....)

示例:
    F(bad)=P(b)*P(a)*P(d)=3*2*7=42

    遍历字典,求每个单词的F()操作值,如果相等就是,不等就下一个

原因：

M个素数和N个素数（M!=N 或 M=N&&素数不完全相同）的乘积不可能相等！可利用整除定理进行反证！

因此这种方法可完美地避免冲突，是一个非常好的hash函数，但是素数相乘，可能会导致溢出问题。

优化：通过按照字母使用词频来分配素数也是值得考虑的,比如元音 a,e,i,u,o 的词频高就分配给2,3,5,7

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

解答2：

取较大的（值比较大，间隔也比较大）素数[p1,p2,……p26]，每个素数代表一个字母，然后每个单词的字母代表的素数相加，作为该单词的特征值，建一个hash或查找树即可。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

解答3：

为了尽可能容纳更多单词，定义36进制，数元为[0~9, A~Z]
每个单词的Key表示为一个长度为26的字符串，每一位分别是字母A~Z在这个单词中出现的次数(n: 0~Z)，
如单词good，Key:00010010000000200000000000

ABCDEFGHIJKLMNOPQRSTUVWXYZ
00010010000000200000000000


输入单词F([A~Z]{0~Z})

1、求F的Key
2、遍历字典，求每个单词的Key，Key相等则为兄弟单词


对比素数积Key，
  优点：不易溢出
  缺点：虽然定义的n在0~Z之间，但还是覆盖不到类似a{37}相同字符出现超过36个的情况，但现有的单词序列中似乎还没有:)

附：

使用此36进制的好处在于，比较KEY时是字符串比较而不是数组的比较（想想单纯使用一个数组来表示每个字母出现的个数的话，则要依次比较每个数组元素是否相同），这样会快很多。

 

更好的解答，欢迎各位推荐。。。。。。。。。。。。。。。。。。。。。。。