Leetcode基础刷题之PHP解析(14. Longest Common Prefix)

2019-6-23 星期天 开始吧

上一题链接Leetcode基础刷题之PHP解析(7. Reverse Integer)

题目描述

这是一道字符串匹配的题，让我们求公共字符串前缀。

题目分析

对于这一类题目，肯定都需要遍历对比一下，先来一种常规的思路，因为只要给定数组中元素当前位置有一个不同，那么公共字符串前缀就是从0截取到当前位置的上一个位置。所以我先随便拿出一个参照点(数组第一个元素)，第一层遍历元素中的值，嵌套循环中遍历数组之后的元素，然后进行对比判断。最后得出结果。

  /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        if(empty($strs)) return "";
        for($i=0;$i<strlen($strs[0]);$i++){
            $temp=$strs[0][$i];
            for($j=1;$j<count($strs);$j++){
                if($i==strlen($strs[$j]) || $strs[$j][$i] != $temp){
                    $strs[0]=substr($strs[0],0,$i);
                }
            }
        }
        return $strs[0];
    }

换一种思路

我们可以使用分而治之的思想啊。每次把数组中的元素分为两个部分，前(左)半部分和后(右)半部分,每次求出半个部分的字符串公共前缀，然后比较两个部分的公共前缀，最后得出整体的公共字符串前缀。这里求数组的中位数可以有三个方法，第一种并不推荐，因为当数值过大时可能会爆表。

    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {

        if(empty($strs)) return "";
        return $this->longCommon($strs,0,count($strs)-1);
    }
    
    function longCommon($strs,$l,$r)
    {
        if($l==$r) return $strs[$l];
        else{
            $mid = $l+(($r-$l)>>1) ;
            $left=$this->longCommon($strs,$l,$mid);
            $right=$this->longCommon($strs,$mid+1,$r);
            return $this->commonPrefix($left,$right);
        }
    }
    
    function commonPrefix($left,$right)
    {
        $min=min(strlen($left),strlen($right));
        for($i=0;$i<$min;$i++){
            if($left[$i] != $right[$i]){
                return substr($left,0,$i);
            }
        }
        return substr($left,0,$min);
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php