leetcode 5 最长回文子串

题目

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例

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

解析

这道题和之前的那道回文的很像:647回文子串，求个数，解法还是动态规划，用动规五部曲分析下：
1、确定DP数组及其含义
这道题的定义方法之前遇到过：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。（是一个true还是false的定义，由于题目是求最长回文串，所以这个dp肯定不能用来当最后的结果）

2、确定递推公式
当s[i] != s[j] 时，那什么都不用说了，肯定是false；
当s[i] == s[j] 时，这就得分情况看下（和之前那道题的分情况套路一样）：

• 若i == j，那就意味是是同一个值，如"a"，那没问题，是回文；
• 若j - i = 1，那意味着是挨着的两个，如"aa"，这样的也是回文，注意是j-i，j比i大；
• 其余的情况，就需要看前一时刻的递推公式怎么样，即dp[i+1][j-1]（注意是谁加谁减）

3、 初始化
二维布尔型dp数组的话，默认初始化是false，但要注意其实dp[i][i]这种的一定是true，可以在初始化的时候赋值好

4、遍历顺序
字符串类型的动规遍历顺序都一样，从左下角到右上角

func longestPalindrome(s string) string {
    n := len(s)
    maxLen := 0
    left := 0
    dp := make([][]bool, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]bool, n+1)
        dp[i][i] = true
    }

    for i := n-1; i >= 0; i-- {
        for j := i+1; j <= n-1; j++ { // 这里是因为上面初始化的时候已经判过了（j:=i也对）
            if s[i] == s[j] {
                if j-i <= 1 || dp[i+1][j-1] == true { // 谁加谁减要分清
                    dp[i][j] = true
                }
            }
            if dp[i][j] == true && j - i > maxLen {
                maxLen = j - i
                left = i
            }
        }
    }
    return s[left: left+maxLen+1]
}

另一种方法是中心扩展法（也不太好理解，还是用动态规划吧）

func longestPalindrome(s string) string {
    n := len(s)
    start, end := 0, 0
    for i := 0; i < n; i++ {
        left1, right1 := expend(s, i, i, n)
        left2, right2 := expend(s, i, i+1, n)
        if right1 - left1 > end - start{
            start, end = left1, right1
        }
        if right2 - left2 > end - start{
            start, end = left2, right2
        }
    }
    return s[start:end+1]
}

func expend(s string, i, j, n int) (int, int) {
    for i >= 0 && j < n && s[i] == s[j] {
        i-- //中心扩展
        j++
    }
    return i+1, j-1
}