5. 最长回文子串

题目#

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

示例 3：

输入：s = "a"
输出："a"

示例 4：

输入：s = "ac"
输出："a"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

思路#

利用中心扩散法检测「回文」子串。由于子串长度可能是奇数或是偶数，因此需要分别处理。

对奇数个字符，中间的单个字符显然是「回文」，需要向它两端依次检测。

对偶数个字符，可以将最中间的「空白」视作回文，向它两端依次检测。

我们对字符串中的每个字符均进行奇、偶处理后，便可获得其中最长的回文子串

代码#

func longestPalindrome(s string) string {
    length := len(s)
    if length < 2 {
        return s
    }

    maxLen := 1
    res := string(s[0])

    for i := 0; i < length-1; i++ {
        oddStr := centerSpread(s, i, i)    // 奇
        evenStr := centerSpread(s, i, i+1) // 偶

        var maxLenStr string
        if len(oddStr) > len(evenStr) {
            maxLenStr = oddStr
        } else {
            maxLenStr = evenStr
        }

        if len(maxLenStr) > maxLen {
            maxLen = len(maxLenStr)
            res = maxLenStr
        }
    }

    return res
}

// left, right 落在同一位置上时，处理奇
// 落在相邻的位置时，处理偶
func centerSpread(s string, left, right int) string {
    length := len(s)
    i, j := left, right
    for i >= 0 && j < length {
        if s[i] == s[j] {
            i--
            j++
        } else {
            break
        }
    }

    // 如 dbcba，从 c 开始处理（奇）
    // 上面跳出循环时，i = 0, j = 4 （此时 s[i] != s[j] 才 break 的）
    // 又 go 里取切片是左闭右开的，即 [low, high)
    // 因此需要取 [i+1, j+1) 返回
    return s[i+1 : j+1]
}