5. 最长回文子串

问题

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

PS:回文是一个正读和反读都相同的字符串，例如，“aba” 是回文，而 “abc” 不是。

例子1：

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

例子2：

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

题解

由于回文串是正读和反读都相同的字符串，因此，对于字符串S来说，S[start]=S[end]，因此，可以根据字符串长度的奇偶性分为两种类型：

1. 奇数长度的回文串，ABCBA型，对于仅有单个字符的字符串，必定为回文串，按照S[start]=S[end]向外扩展，得到的也一定是回文串。
2. 偶数长度的回文串，ABCCBA型，对于偶数长度的回文串，其中间部分必定为两个连续的相同字符，再按照S[start]=S[end]向外扩展，得到的也一定是回文串。

因此，

func longestPalindrome(s string) string {
    maxLengthStr := ""
    for i := 0; i < len(s); i++ {
        // 对于1情况进行处理
        s1 := checkLongestPalindrome(s, i, i+1)
        var s2 string
        // 对于2情况进行处理
        // 最小回文串首尾相同
        if i+1 < len(s) && s[i] == s[i+1] {
            s2 = checkLongestPalindrome(s, i, i+2)
        }
        //记录最长回文串
        if len(s1) > len(maxLengthStr) {
            maxLengthStr = s1
        }
        if len(s2) > len(maxLengthStr) {
            maxLengthStr = s2
        }
    }
    return maxLengthStr
}

// 用于扩展子串
func checkLongestPalindrome(s string, start int, end int) string {
    // 错误检测
    if start >= 0 && end <= len(s) && start < end {
        for true {
            // 如果首尾相同，且不越界，则不断扩展
            if start-1 >= 0 && end < len(s) && s[start-1] == s[end] {
                start--
                end++
            } else {
                break
            }
        }
        return s[start:end]
    } else {
        return ""
    }
}