大家好,又见面了,我是你们的朋友全栈君。
由于case包含奇偶性,所以分两种情况讨论
思路:找到以字符”x”为中心的最长回文子串
- 从x的下标开始遍历,拆分为偶数对称情况和奇数对称情况
- 终止条件有2:
- 对称位置的字符不相同
- 循环右侧下标超出字符长度
结果:1364 ms 14.9 MB
主要难点是:计算下标
代码:
class Solution
{
/**
* @param String $s
* @return String
*/
function longestPalindrome($s)
{
$sArray = str_split($s, 1);
$length1 = 1;
$length2 = 1;
$max = 1;
$maxS = $sArray[0];
$subS1 = $sArray[0];
$subS2 = $sArray[0];
$sLength = sizeof($sArray);
for ($i = 0; $i < $sLength; $i++) {
$bool1 = false;
$bool2 = false;
for ($j = $i; $j >= 0; $j--) {
if ($sLength > 2) {
// 奇数情况
if ($sArray[$i - 1] == $sArray[$i + 1] && !$bool2 && (2 * $i - $j) <= $sLength - 1) {
$length2 = 2 * ($i - $j) + 1;
$subS2 = substr($s, $j, $length2);
if ($sArray[$j] != $sArray[2 * $i - $j]) {
$length2 = 2 * ($i - $j) - 1;
$subS2 = substr($s, $j + 1, $length2);
$bool2 = true;
}
}
}
// 偶数情况
if ($sArray[$i] == $sArray[$i + 1] && !$bool1 && (2 * $i - $j + 1) <= $sLength - 1) {
$length1 = 2 * ($i - $j + 1);
$subS1 = substr($s, $j , $length1);
if ($sArray[$j] != $sArray[2 * $i - $j + 1]) {
$length1 = 2 * ($i - $j);
$subS1 = substr($s, $j + 1, $length1);
$bool1 = true;
}
}
if ($bool1 && $bool2) {
break;
}
}
$length = $length1 > $length2 ? $length1 : $length2;
$subS = $length1 > $length2 ? $subS1 : $subS2;
if ($length > $max) {
$maxS = $subS;
$max = $length;
}
if (($sLength - $i - 1) * 2 <= $max) {
break;
}
}
return $maxS;
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/135660.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...