题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

回文子串 是指一个字符串从前往后读和从后往前读是完全相同的字符串。

示例

输入: "babad" 输出: "bab" 或 "aba"

输入: "cbbd" 输出: "bb"

PHP 示例代码

function longestPalindrome($s) {
    $n = strlen($s);
    if ($n < 2) {
        return $s;
    }

    $start = 0;
    $maxLength = 1;

    // 辅助函数，用于检查回文
    function expandAroundCenter($left, $right, $s) {
        while ($left >= 0 && $right < strlen($s) && $s[$left] == $s[$right]) {
            $left--;
            $right++;
        }
        return strlen($s) - $right + $left + 1;
    }

    // 遍历所有可能的中心
    for ($i = 0; $i < $n - 1; $i++) {
        // 奇数长度回文
        $len1 = expandAroundCenter($i, $i, $s);
        // 偶数长度回文
        $len2 = expandAroundCenter($i, $i + 1, $s);
        $len = max($len1, $len2);

        // 如果当前长度大于已知的最大长度，则更新
        if ($len > $maxLength) {
            $start = $i - floor(($len - 1) / 2);
            $maxLength = $len;
        }
    }

    return substr($s, $start, $maxLength);
}

// 测试示例
echo longestPalindrome("babad"); // 输出: bab 或 aba
echo longestPalindrome("cbbd");  // 输出: bb

Python 示例代码

def longestPalindrome(s: str) -> str:
    if len(s) < 2:
        return s

    start, maxLength = 0, 1

    def expandAroundCenter(left: int, right: int) -> int:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

    for i in range(len(s) - 1):
        # 奇数长度回文
        len1 = expandAroundCenter(i, i)
        # 偶数长度回文
        len2 = expandAroundCenter(i, i + 1)
        max_len = max(len1, len2)

        if max_len > maxLength:
            start = i - (max_len - 1) // 2
            maxLength = max_len

    return s[start:start + maxLength]

# 测试示例
print(longestPalindrome("babad"))  # 输出: bab 或 aba
print(longestPalindrome("cbbd"))   # 输出: bb

JavaScript 示例代码

function longestPalindrome(s) {
    let start = 0, maxLength = 1;

    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    for (let i = 0; i < s.length - 1; i++) {
        let len1 = expandAroundCenter(i, i); // 奇数长度
        let len2 = expandAroundCenter(i, i + 1); // 偶数长度
        let len = Math.max(len1, len2);

        if (len > maxLength) {
            start = i - Math.floor((len - 1) / 2);
            maxLength = len;
        }
    }

    return s.substr(start, maxLength);
}

// 测试示例
console.log(longestPalindrome("babad")); // 输出: bab 或 aba
console.log(longestPalindrome("cbbd"));  // 输出: bb

码小课网站中有更多相关内容分享给大家学习，希望这些示例代码能帮助到你！