blog 算法之美

现在是凌晨三点三十八分 :)

本来我一点钟的时候是准备睡的，然而正准备关灯的时候，我一不小心瞟到了角落的《数据结构与算法 JavaScript 描述》（下面简称《算法》）。

这本书刚买回来时，我简单翻了一下前两章，然后就后悔买这本书了：书上讲的都是很基础的内容，第一章完全就是给 JavaScript 新手看的，第二章讲了 Array 的一些方法，而这些内容我早在《JavaScript 权威指南》里面就看过了。

这也是这本书一直被我放在角落的原因。

为了避免自己去睡觉（明明很困但就是不想睡），我翻了翻这本书，发现第二章有四个习题，粗略看了看也不难，正好拿来清醒一下大脑。

前三题没什么难度，轻松完成。但是第四题却让我意识到，这本书可能没我想像中的那么简单：

创建这样一个对象，它将字母存储在数组中，并且用一个方法可以将字母连在一起，显示成一个单词。

我先试着理解了一下题目。它似乎是要实现这样一个函数，我们假设它叫 word：

word( 'o', 'n' ); // 输出单词 no
word( 's' , 'y' , 'e' ); // 输出单词 yes
word( 'j', 'v', 'a', 'a' ); // 输出单词 java
word( 'c', 'i', 's', 't', 'p', 'r' ); // 输出单词 script

这道题跟前面三题、跟前两章给 js 新手看的内容根本不是一个级别啊！！

按照我的思路，我首先得列出输入的这几个字母所能组合成的所有字符串，然后再验证它是不是一个有效的单词。例如上面的 ['s','y','e'] 可以组合成：

sye sey
yse yes
esy eys

而其中只有 yes 是英文单词。

……好难！我只是一个前端，在工作中从来没碰到这样的场景啊！！但这却激起了我的兴趣，我的瞌睡一下子就没了。

为了方便我理解字母组合成单词的过程，我专门画了一张图：（我知道这图很 low，将就看一下吧 - -）

如图所示，单词的组建过程其实就是一个树状结构。即使我知道了这一点，可是我怎么知道它所有的路径呢？

我尝试从字母个数与组合结果这两个数据之间寻找联系。我注意到这么个规律：

字母的个数       组合结果
  1              1
  2              2
  3              6
  4             24

虽然我算不出其中的规律，但是我总觉得这种结构在哪见过，我记得《JavaScript 语言精粹》里面好像讲到过一个斐什么那什么的数列，而这本《算法》好像也在哪提到过。往书的前面翻了翻，果然，它在第 1.2.7 节里讲解“递归”的时候用到了这个函数（虽然书上没说这个函数跟一个数列有关，但函数的名字我还是记得的）：

function factorial(number) {
  if (number == 1) {
    return number;
  } else {
    return number * factorial(number -1);
  }
}

由此可以算出，当字母的个数有 5 个时，最终组合出来的结果有 1 * 2 * 3 * 4 * 5 = 120 个。

可是知道这一点对我没有任何帮助，我需要一个遍历这颗“树”的方法，从而得到最终这 120 个组合结果。

我把这棵树从“分层”的角度来看，每一层都要比上一层少一个节点，而这一层就是由从上一层里面剩余的几个节点组成的（我知道很绕口）。根据这个想法，半小时后，我的第一版出来了：

// 复制（或将类数组转换为真）数组的辅助函数
function copyArr( arr ) {
    return [].slice.call( arr , 0 );
}

function list() {
    var args   = copyArr( arguments ) ,
        length = args.length ,
        tree   = [];

    for ( var i = 0 ; i < length ; i += 1 ) {
        var layer = [];
        layer.push( args[ i ] ); // 依次抽出元素
        args.forEach( function ( v , index ) {
            if ( i !== index ) {
                layer.push( v ); // 将剩余元素加到层中
            }
        } );
        tree.push( layer );
    }
    console.log( tree );
    return tree;
}

很明显这是不对的……执行 list( 's', 'y', 'e') 之后，控制台只输出了三个结果：

[ [ 's', 'y', 'e' ], [ 'y', 's', 'e' ], [ 'e', 's', 'y' ] ]

苦思冥想一番，发现真是没什么头绪，就像一头狼看到了一个刺猬，不知道从哪里下嘴。终于，半个小时过后我放弃了，把书往旁边一扔，关灯睡觉。

我躺下之后，脑海里仍然还想着上面那幅图，突然大脑里灵光一闪：当我躺下来的时候，那幅图也跟着逆时针旋转了 90 度，原本的树结构变成了很容易理解的“对象”。例如 [ 's', 'y', 'e' ] 的样子变成了下面这样：

{
  s:{
     y:{
        e:{} // sye
     },
     e:{
         y:{} // sey
      }
  }
  // ...下面类似，不再列出
}

从这个角度看的话，思路一下就明了了：我只需要一层层生成这棵树就可以了！就如上面所说，下一层比上一层少一个元素，所以我需要一个将某个元素从数组中抽离的方法，而一层层的生成树肯定要用到递归！

我一下子从床上弹了起来，赶紧重新开了电脑（关闭了还没半分钟），然后写下了第二版：

// 将 arr 中的 element 抽离，并返回抽离之后的新数组
function spliceFormArr( arr , element ) {
    var i = arr.indexOf( element ) ,
        c;
    if ( i >= 0 ) {
        c = copyArr( arr );
        c.splice( i , 1 );
    }
    return c;
}

function list() {
    var args = copyArr( arguments ) ,
        root = {};

    subTree( root , args );
    console.log( root );
    return root;

    // 生成子树的方法
    function subTree( root , arr ) {
        // 当子树里最终一个节点都没有的时候，这里就不会执行 forEach 了
        arr.forEach( function ( v , i , a ) {
            // 为子树上的每一个节点创建一个对象，并在下一层中抽离父节点
            subTree( root[ v ] = {} , spliceFormArr( a , v ) );
        } );
    }
}

信心满满的执行了 list( 's', 'y', 'e')，结果如下：运算结果真是太棒了！！关键点攻破之后，重复字母、性能优化、单词匹配等问题也就不难了——一步步解开一个题目的感觉真是太好了！！