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

2019-5-15 星期三  开始吧

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

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

题目描述

给定一个字符串，让我们求它的最长回文子串，关于回文不了解的可以自行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