5 最长回文子串（区间 dp）

1. 问题描述：

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

示例 1：

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

示例 2：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring/

2. 思路分析：

这道题目类似于最长回文子序列的问题，而子串的限制要求字符串是连续的，但是也是类似的思路，因为同样是求解一个区间中满足某个限制的问题，所以可以使用区间 dp 来解决，只是在状态计算的时候会有些不一样，只需要细微调整一下即可，对于长度为 1 的子串那么回文串的长度为  1；对于长度为 2 的子串判断 s[i] == s[j]，相等则为 2；长度大于 2 的子串判断 s[i] == s[j] 并且 f(i + 1，j - 1) 大于 0 说明 s[i + 1:j - 1] 才是回文串。

3. 代码如下：

python（超时）：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        f = [[0] * (n + 10) for i in range(n + 10)]
        res = ""
        # 经典的区间dp框架, 枚举长度
        for l in range(1, n + 1):
            # 枚举起点i
            i = 0
            while i + l - 1 < n:
                # j为当前起点为i长度为l的区间终点
                j = i + l - 1
                if l == 1:
                    f[i][j] = 1
                elif l == 2:
                    if s[i] == s[j]:
                        f[i][j] = 2
                else:
                    if s[i] == s[j] and f[i + 1][j - 1]:
                        f[i][j] = f[i + 1][j - 1] + 2
                if f[i][j] > len(res):
                    res = s[i: j + 1]
                i += 1
        return res

go：

package main

import "fmt"

func longestPalindrome(s string) string {
	n := len(s)
	f := make([][]int, n+10)
	for i := 0; i < n+10; i++ {
		f[i] = make([]int, n+10)
	}
	res := ""
	for l := 1; l <= n; l++ {
		i := 0
		for ; i+l-1 < n; i++ {
			j := i + l - 1
			if l == 1 {
				f[i][j] = 1
			} else if l == 2 {
				if s[i] == s[j] {
					f[i][j] = 2
				}
			} else if s[i] == s[j] && f[i+1][j-1] > 0 {
				f[i][j] = f[i+1][j-1] + 2
			}
			if f[i][j] > len(res) {
				res = s[i : j+1]
			}
		}
	}
	return res
}

中心扩展解法：

python：

class Solution:
    def get(self, i: int, j: int, s: str, res: str):
        t = ""
        while i >= 0 and j < len(s) and s[i] == s[j]:
            t = s[i: j + 1]
            i -= 1
            j += 1
        if len(t) > len(res):
            res = t
        return res

    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        res = ""
        for i in range(n):
            res = self.get(i, i, s, res)
            res = self.get(i, i + 1, s, res)
        return res

go：

package main

import "fmt"

func get(i int, j int, s string, res string) string {
	t := ""
	for i >= 0 && j < len(s) && s[i] == s[j] {
		t = s[i : j+1]
		i -= 1
		j += 1
	}
	if len(t) > len(res) {
		res = t
	}
	return res
}

func longestPalindrome(s string) string {
	n := len(s)
	res := ""
	for i := 0; i < n; i++ {
        // 若当前的回文串为奇数
		res = get(i, i, s, res)
        // 若当前的回文串为偶数
		res = get(i, i+1, s, res)
	}
	return res
}