leetcode-5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"

解题思路一：中心扩展算法

1．回文是一个正读和反读都相同的字符串
2．回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n - 1 个这样的中心。
3．为什么会是 2n - 1 个，而不是 n 个中心？比如有字符串abcba，这时回文子串是abcda，中心是c；又有字符串adccda，这时回文子串是adccda，中心是cc。 由此可见中心点既有可能是一个字符，也有可能是两个字符，当中心为一个字符的时候有n个中心，当中心为两个字符的时候有n-1个中心，所以一共有2n-1个中心。
4．然后for循环开始从左到右遍历，为什么会有两次　expandAroundCenter，一次是i和i本身，一次是i和i+1，这就是上面说到的一个中心与两个中心。
5．而后会去判断这两种情况下谁的回文子串最长，并标记出这个子串在原字符串中的定位，即start和end。

<?php

class Solution
{
    /**
     * 获取最长回文子串
     * @param $str
     * @return false|string
     */
    public function longestPalindrome($str)
    {
        if ($str == null || strlen($str) < 1) return "";
        $start = 0; //　最大回文子串起始下标
        $end = 0;// 最大回文子串结束下标
        for ($i = 0; $i < strlen($str); $i++) {
            $len1 = $this->expandAroundCenter($str, $i, $i);//单个字符为中心
            $len2 = $this->expandAroundCenter($str, $i, $i + 1);//两个字符为中心
            $len = max($len1, $len2);//获取两者最长子串
            if ($len > $end - $start) {//调整起始和结束下标
                $start = $i - intval(($len - 1) / 2);
                $end = $i + intval($len / 2);
            }
        }
        return substr($str, $start, $end - $start + 1);
    }

    /**
     * 获取以left right为中心的回文字段长度
     * @param $str
     * @param $left
     * @param $right
     * @return int　回文子串的长度
     */
    private function expandAroundCenter($str, $left, $right)
    {
        while ($left >= 0 && $right < strlen($str
            ) && $str[$left] == $str[$right]) {
            $left--;
            $right++;
        }
        return $right - $left - 1;
    }

}
$solution = new Solution();
$str = 'cbbd';
echo ($solution->longestPalindrome($str)) . PHP_EOL;
$str = 'cbabcd';
echo ($solution->longestPalindrome($str)) . PHP_EOL;
bb
cbabc

时间复杂度：O(n^2)
空间复杂度：O(1)

解题思路二：最长公共子串

根据回文串的定义，正着和反着读一样，那我们是不是把原来的字符串倒置了，然后找最长的公共子串就可以了。例如 S = "caba" ，S = "abac"，最长公共子串是 "aba"，所以原字符串的最长回文串就是 "aba"。

关于求最长公共子串（不是公共子序列），有很多方法，这里用动态规划的方法，整体思想就是，申请一个二维的数组初始化为 0，然后判断对应的字符是否相等，相等的话arr [ i ][ j ] = arr [ i - 1 ][ j - 1] + 1。当 i = 0 或者 j = 0 的时候单独分析，字符相等的话 arr [ i ][ j ] 就赋为 1 。
arr [ i ][ j ] 保存的就是公共子串的长度。

image.png
image.png

<?php
error_reporting('EALL & Notice');

class Solution
{
    /**
     * 获取最长回文子串
     * @param $str
     * @return false|string
     */
    public function longestPalindrome($str)
    {
        $len = strlen($str);
        if ($str == null || $len < 1) return "";
        $reverse = strrev($str);
        $maxLen = 0;// 最大回文子串长度
        $maxEnd = 0;// 最大回文子串结束下标
        $arr = array(array());
        for ($i = 0; $i < $len; $i++) {
            for ($j = 0; $j < $len; $j++) {
                if ($str[$i] == $reverse[$j]) {
                    if ($i == 0 || $j == 0) {
                        $arr[$i][$j] = 1;
                    } else {
                        $arr[$i][$j] = $arr[$i - 1][$j - 1] + 1;
                    }
                }
                if ($arr[$i][$j] > $maxLen) {
                    $beforeRev = $len - $j - 1;// 反转前起始下标
                    if($beforeRev + $arr[$i][$j] - 1 == $i){//判断下标是否对应
                        $maxLen = $arr[$i][$j];
                        $maxEnd = $i;

                    }

                }

            }

        }
        return substr($str, $maxEnd - $maxLen + 1, $maxLen);
    }

}

$solution = new Solution();
$str = 'cbb';
echo ($solution->longestPalindrome($str)) . PHP_EOL;
$str = 'cbabcd';
echo ($solution->longestPalindrome($str)) . PHP_EOL;
$str = 'abc43cba';
echo ($solution->longestPalindrome($str)) . PHP_EOL;
结果：
bb
cbabc
a

时间复杂度：两层循环 O(n²)。
空间复杂度：一个二维数组 O(n²)。