给定一个字符串 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 ] 保存的就是公共子串的长度。
<?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²)。
