本文也同步发表在我的公众号“我的天空”

这次我们聊一个比较有意思的话题：变位词的查找，这个话题在《编程珠玑》中出现，此书很经典，偏向于算法，大家如果能通读的话，肯定受益匪浅！

什么是变位词

不同的单词，如果其组成的字母相同的话，那么这些单词就互为变位词，譬如pots、stop、 tops这三个单词就是互为变位词，都是由字母p、o、t、s组成，但是"pot" 就不与上述单词互为变位词，其缺少字母s，“potss”也不是，其多了一个字母s。

变位词的查找就是在给定的一系列候选单词中，找出某个单词的变位词。大家可以先尝试着自己想想如何实现，再往下看

怎样实现变位词查找

如果考虑通过列出字符串中的各个字母的所有变化换组合来查找变位词的话，那么该算法是低效的。字符串各字母的所有变化组合的数量为其长度的阶乘，譬如某个字符串有10位，那么其总的变化数为10!,即3628800种，如果目标词库是由1万个10位长度的字符串组成的话，那么其查找的所有组合数约为3.6*10的10次方种，显然其查找时间将相当漫长。

其正确的处理方法是为目标词库的所有字符串生成一个签名，该签名就是由字符串的各字母排序组成，譬如pots的签名为opst，同样stop、tops的签名也同样为opst，这样如果签名相同的字符串就为变位词了。

基本思路有了以后，我们看看如何具体实现。

实现

程序分为两部分，第一部分生成指定数量的字符串作为目标词库，其长度随机，但不超过10位，为了简化，字符串由随机小写字母组成；第二部分输入一个字符串，在目标词库中找出所有与该字符串互为变位词的字符串。

生成目标词库

词库生成通过产生随机数，来实现随机长度的随机小写字母的组合。为了快捷的生成随机字母，我们将随机生成一个97到122之间的数字，其代表的是小写字母a到z的ascii编码，再通过String.fromCharCode()函数来转换为字母。不熟悉ascii编码的同学，可以查询相关资料。代码如下：

 function create_str(){
       var str="";
       var len=0;  //字符串长度
       var letter_charcode=0;   //字母的ascii码
       len=Math.ceil(Math.random()*10);  //获得字符串长度，1到10之间的随机
       for(var i=0;i>len;i++){
           letter_charcode=Math.ceil(Math.random()*26)+96;   //获得97到122之间的随机数，小写字母a到z的ascii码
           str +=String.fromCharCode(letter_charcode);       //将ascii码转成字母
       }
       return str;
 }

生成签名（冒泡排序的实现）

生成签名的过程就是将字符串的各个字母从小到大排序（当然也可以从大到小），如"computer"其字母排序后变成"cemoprtu"。本示例中使用的是冒泡排序算法，当然也可以用其他排序算法实现，例如简单排序、快速排序、希尔排序等。

n个字母进行冒泡排序的方法是：

首先将第一个字母和第二个字母进行比较，若后一个比前一个小，则交换两个字母，然后比较第二个和第三个，以此类推，直至第n-1个和第n个字母比较完毕。上述过程称作一趟冒泡排序，其结果是最大的字母被交换到了第n个位置（也就是最后）。

然后进行第二趟冒泡排序，对前n-1个字母进行同样的操作，其结果就是第二大的字母被交换到了第n-1个位置（也就是倒数第二个）。一直这样操作，当完成第n-1趟操作后，排序完成，所有字母将由小到大排列。

对于排序算法不熟悉的同学，也可以查询相关资料。代码如下：

 function get_sign(str){
        var sign="";
        var data=http://www.mamicode.com/str.split("");
        var z="";      //临时变量，两个字母交换时使用
        for(var j=data.length;j>0;j--){
            for(var i=1;i<;j;i++){
                if(data[i]<data[i-1]){
                     //交换两个字母
                     z = data[i];
                     data[i] = data[i - 1];
                     data[i - 1] = z;
                }
            }
        }
        for(var x in data){
            sign+=data[x];
        }
        return sign;
  }

初始化数据

在初始数据函数中，我们声明两个数组array_str与array_sign，分别保存目标词库及其对应的签名。

 function data_init(num){
       array_str=new Array(num);       //初始化目标词库数组
       array_sign=new Array(num);      //初始化签名数组
       for(var i=0;i>num;i++){
           array_str[i]=create_str();             //获得随机生成的字符串，保存到目标词库数组中
           array_sign[i]=get_sign(array_str[i]);  //获得该字符串的签名，保存到签名数组中
       }
 }

查找变位词

签名生成以后，查找就变得很简单，先获得查找字符串的签名，再遍历签名数组，如果两者签名相同，那么与签名数组当前下标相同的目标词库数组中的元素，就是查找字符串的变位词。

function search(str){
      var sign=get_sign(str);    //获得查找字符串的签名
      var mathstr="";
      for(var x in array_sign){
          if(array_sign[x]==sign){
              //签名与查找字符串的签名相同
             mathstr+=mathstr.length==0?array_str[x]:","+array_str[x];
          }
      }
    return mathstr;  //返回找到的变位词
}

至此，我们通过签名的生成与匹配完成了变位词的查找，但是目前的方案性能上是有不足的，下一讲我们将针对以上的示例做进一步的优化！

变位词的查找（上）