Leetcode基础刷题之PHP解析(5. Longest Palindromic Substring )

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

内容简介:做了今天这一题动态规划题目,明天开始可以选一些动态规划的题目了。

2 0 1 9 -5 -15   期三    

做了今天这一题动态规划题目,明天开始可以选一些动态规划的题目了。

Leetcode基础刷题之 PHP 解析(3. Longest Substring Without Repeating )

Leetcode基础刷题之PHP解析(5. Longest Palindromic Substring )

给定一个字符串,让我们求它的最长回文子串,关于回文不了解的可以自行Google。

好吧第一遍使用的是暴力破解,然后愉快的超时了,思路也很简单,从头开始遍历每次截取到当前位置的字符串进行反转判断是否相等,如果相等说明此时到当前位置的字符串是回文,如果当前回文的子串大于之前最长回文子串,更新最长回文子串即可,是不是和昨天思路很相似。

/**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
        if(strlen($s)<2){
            return $s;
        }
        $max=$s[0];
        for($i=0;$i<strlen($s);$i++){
            for($j=$i+1;$j<strlen($s);++$j){
                $str=substr($s,$i,$j-$i+1);
                $strrev=strrev($str);
                if($str==$strrev && strlen($str)>strlen($max)){
                    $max=$str;
                }
            }
        }
        return $max;
    }

动态规划

我们可以维护一个二维数组来表示一个区间内是否为回文串($[$i][$j]),当$i=$j的时候,说明此时只是一个字符串,那么肯定是回文串,如果$i-$j等于1说明此时他们是相邻的两个字符串,只需要判断$s[$i]是否等于$s[$j],如果相减大于等于2的话,说明他们之间不是相邻的,相当于此时$i位于当前字符串的最右侧,$j位于当前字符串的最左侧,我们除了判断他们自身是否相等之外,还需要判断$s[$i-1]和$s[$j+1]是否相等,也就是需要一一对应。最后再截取一下。

/**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
         if(strlen($s)<2){
            return $s;
        }
        $dp=[];
        $left=$right=$len=0;
        for($i=0;$i<strlen($s);$i++){
            $dp[$i][$i]=1;
            for($j=0;$j<$i;++$j){
                $dp[$j][$i]=($s[$i]==$s[$j] && ($i-$j <2 || $dp[$j+1][$i-1]));
                if($dp[$j][$i] && $len < $i-$j+1){
                    $len=$i-$j+1;
                    $left=$j;
                    $right=$i;
                }
                
            }
        }
        return substr($s,$left,$right-$left+1);
   
    }

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


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

查看所有标签

猜你喜欢:

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

The Probabilistic Method Second Edition

The Probabilistic Method Second Edition

Noga Alon、Joel H. Spencer / Wiley-Blackwell / 2000 / $121.95

The leading reference on probabilistic methods in combinatorics-now expanded and updated When it was first published in 1991, The Probabilistic Method became instantly the standard reference on one......一起来看看 《The Probabilistic Method Second Edition》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

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

在线图片转Base64编码工具

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

Base64 编码/解码