5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：”bb”

示例 3：
输入：s = “a”
输出：”a”

示例 4：
输入：s = “ac”
输出：”a”

思路：动态规划，第i-j 是否回文，回文的判断标准是

<?php
class Solution {
    /**
     * @param String $str
     * @return String
     */
    function longestPalindrome($str) {
        $len = strlen($str);
        if ($len < 2){
            return $str;
        }
        $dp = [];
        // 第i-i 肯定是回文的
        for ($i = 0; $i<$len; $i++){
            $dp[$i][$i] = true;
        }
        $maxLen = 1;
        $start = 0;
        for ($j = 1;$j < $len ; $j++){
            for ($i = 0 ; $i < $j ; $i++){
                $left = substr($str,$i,1);
                $right = substr($str,$j,1);
                $dp[$i][$j] = ($left == $right) && (($j - $i) < 3 || $dp[$i + 1][$j - 1]);
                if (!empty($dp[$i][$j])){
                    $currentMaxLen = $j-$i+1;
                    if ($currentMaxLen > $maxLen){
                        $maxLen = $currentMaxLen;
                        $start = $i;
                    }
                }
            }
        }
        return substr($str,$start,$maxLen);
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。