php 最长回文子串

全栈程序员-站长 • 2022年6月4日下午8:00 • 未分类 • 阅读 35

大家好，又见面了，我是你们的朋友全栈君。

最长回文子串

由于case包含奇偶性，所以分两种情况讨论

思路：找到以字符”x”为中心的最长回文子串

从x的下标开始遍历，拆分为偶数对称情况和奇数对称情况
终止条件有2：
1. 对称位置的字符不相同
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;
    }
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/135660.html原文链接：https://javaforall.net