5.最长回文子串.md

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 仅由数字和英文字母（大写和/或小写）组成

解法

回文直接dp求解即可，过程中维护最长串

func longestPalindrome(s string) string {
    if len(s) <= 1 {
        return s
    }
    dp := make([][]bool, len(s))
    for i := range dp {
        dp[i] = make([]bool ,len(s))
    }
    res := string(s[0]) // 给个默认首字符
    for i := len(s)-1; i >= 0; i-- {
        for j := i; j < len(s); j++ {
            if s[i] == s[j] {
                dp[i][j] = true
                // aba这种，也是true
                if i+1 <= j-1 {
                    dp[i][j] = dp[i+1][j-1]
                }
                if dp[i][j] && j-i+1 > len(res) {
                    res = s[i:j+1]
                }
            }
        }
    }
    return res
}