php程序员面试之百度面试题

据说是一个百度php的面试题，已给定一个数组：

$arr = array(‘b’=>’a’, ‘c’=>’a’, ‘e’=>’b’, ‘d’=>’b’, ‘f’=>’c’, ‘g’=>’e’, ‘h’=>’f’);

写一个算法，完成到以下格式的转换：

array (

    'a' => array (

        'b' => array (

            'e' => array (

                [0] => 'g',

            ),

            [0] => 'd',

        ),

        'c' => array (

            'f' => array (

                [0] => 'h',

            ),

        ),

    ),

)

这个结构应该属于一种Trie树。当时在写的时候由于没发现array_keys()函数第二个参数(汗一个先)，于是写了以下这个方法来实现。

function getsomething(&$arr, &$re, $c='') {

    $c or $c=array_shift(array_keys($arr));//当未指定开始位置时 从数组第一个元素开始

    $flag= false;   //标记 当有和$c对应的key(键)时 设为true

    while($k = array_search($c, $arr)) {    //循环获取值为$c的key。

        getsomething($arr, $re[$c], $k);    //一直递归到最后没有key对应时

        unset($arr[$k]);        //移除  这个元素已经不会再使用了

        $flag = true;

    }

    //当flag为真时 说明之前获得过正常存在的key，不会继续生成[0]下标的元素

    if(! $flag) return $re[] = $c; 

}

//调用

getsomething($arr, $re, 'a');

虽然有点儿奇葩，至少还是实现了。以下是某网友使用array_keys()的另一解法：

function _array_keys($k, $arr) {

    $return = array();

    if($ret = array_keys($arr, $k)) {

        foreach($ret as $v) {

            if($t = _array_keys($v, $arr)) {

                $return[$v] = $t;

            } else {

                $return[] = $v;

            }

        }

    }

    return $return;

}