长回文子串-动态规划解法

发布时间 2023-08-31 18:10:31作者: _春华秋实

题目:

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

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

示例 1:

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

Golang 代码示例

上面三行对应循环三次的执行逻辑

逻辑视频讲解

func longestPalindrome(s string) string {
	//根据字符长度初始化一个二维数组,下标对应字幕的位置
	dp := make([][]bool, len(s))
	for i := 0; i < len(s); i++ {
		dp[i] = make([]bool, len(s))
	}
	ans := ""
	for i := 0; i < len(s); i++ {
		for k := 0; k <= i; k++ {
			//前后字符相同 && 中间的字符也是回文串
			dp[i][k] = s[i] == s[k] && (i-1 < k+1 || dp[i-1][k+1])
			if dp[i][k] && i-k+1 > len(ans) {
				ans = s[k : i+1]
			}
		}
	}
	return ans
}