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

栏目: PHP · 发布时间: 5年前

内容简介:2019-6-23 星期天 开始吧

2019-6-23 星期天 开始吧

Leetcode基础刷题之 PHP 解析(7. Reverse Integer)

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

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

对于这一类题目,肯定都需要遍历对比一下,先来一种常规的思路,因为只要给定数组中元素当前位置有一个不同,那么公共字符串前缀就是从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


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Learn Python the Hard Way

Learn Python the Hard Way

Zed Shaw / Example Product Manufacturer / 2011

This is a very beginner book for people who want to learn to code. If you can already code then the book will probably drive you insane. It's intended for people who have no coding chops to build up t......一起来看看 《Learn Python the Hard Way》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具