5. 最长回文子串

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

解题思路：动态规划

这里存在三种情况：

1. 整个字符串都是回文字符串。
2. 字符串是连续相同的。
3. 上面两种情况之外的情况。

func longestPalindromeN(s string) string {
    if len(s) < 2 { // 肯定是回文，直接返回
        return s
    }
    begin, maxLen := 0, 1
    for i := 0; i < len(s); {
        if len(s)-i <= maxLen/2 { // 第一种情况
            break
        }
        b, e := i, i
        for e < len(s)-1 && s[e+1] == s[e] { // 第二种情况
            e++
        }
        i = e + 1 // 下一个回文的`正中间段`的首字符只会是s[e+1]
        for e < len(s)-1 && b > 0 && s[e+1] == s[b-1] { // 第三种情况
            e++
            b--
        }
        newLen := e + 1 - b
        if newLen > maxLen {
            begin = b
            maxLen = newLen
        }
    }
    return s[begin : begin+maxLen]
}

结果：

附

下一题传送门