题目描述补充

题目：最长回文子串

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

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:

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

PHP 示例代码

function longestPalindrome($s) {
    $n = strlen($s);
    if ($n < 2) {
        return $s;
    }
    
    $start = 0;
    $maxLength = 1;
    
    for ($i = 0; $i < $n - 1; $i++) {
        // 奇数长度的回文
        $len1 = expandAroundCenter($s, $i, $i);
        // 偶数长度的回文
        $len2 = expandAroundCenter($s, $i, $i + 1);
        // 取两种情况的较大者
        $len = max($len1, $len2);
        
        // 如果当前找到的回文子串比之前找到的更长，则更新起始位置和最大长度
        if ($len > $maxLength) {
            $start = $i - floor(($len - 1) / 2);
            $maxLength = $len;
        }
    }
    
    return substr($s, $start, $maxLength);
}

function expandAroundCenter($s, $left, $right) {
    $L = $left;
    $R = $right;
    while ($L >= 0 && $R < strlen($s) && $s[$L] == $s[$R]) {
        $L--;
        $R++;
    }
    // 注意，循环结束后，L 和 R 已经越界，所以长度需要加 1 后再减 2
    return $R - $L - 1;
}

// 示例用法
echo longestPalindrome("babad");  // 输出: bab 或 aba

Python 示例代码

def longestPalindrome(s: str) -> str:
    if len(s) < 2:
        return s
    
    start, max_length = 0, 1
    
    for i in range(len(s)):
        # 奇数长度的回文
        len1 = expandAroundCenter(s, i, i)
        # 偶数长度的回文
        len2 = expandAroundCenter(s, i, i + 1)
        
        # 保留最大长度回文的起始位置和长度
        max_len = max(len1, len2)
        if max_len > max_length:
            start = i - (max_len - 1) // 2
            max_length = max_len
    
    return s[start:start + max_length]

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

# 示例用法
print(longestPalindrome("babad"))  # 输出: bab 或 aba

JavaScript 示例代码

function longestPalindrome(s) {
    let start = 0, maxLength = 1;
    
    const n = s.length;
    if (n < 2) return s;
    
    function expandAroundCenter(left, right) {
        let L = left, R = right;
        while (L >= 0 && R < n && s[L] === s[R]) {
            L--;
            R++;
        }
        return R - L - 1;
    }
    
    for (let i = 0; i < n - 1; i++) {
        const len1 = expandAroundCenter(i, i); // 奇数长度
        const len2 = expandAroundCenter(i, i + 1); // 偶数长度
        const 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

码小课 网站中有更多关于算法和数据结构的相关内容分享，包括视频教程、代码实现、解题技巧等，欢迎大家学习交流。