5. 最长回文子串

发表于： 分类于：
字数： 328 阅读：≈ 1分钟 浏览：

https://leetcode.cn/problems/longest-palindromic-substring/

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

  1. 动态规划，某一个区间为动态规划的值 dp[i][j] 表示从 i 到 j 是否满足回文子串

代码 


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))
		// 只有一个值，一定是回文子串
		dp[i][i] = true
	}

	var maxLen int
	var res string
	maxLen = 1
	res = string(s[0])
	// l 表示子串的长度
	for l := 2; l <= len(s); l++ {
		for i := 0; i < len(s); i++ {
			j := i+l-1
			if j >= len(s) {
				break
			}
			if s[i] == s[j] {
				if j-1 - (i+1) <= 0 {
					dp[i][j] = true
				} else {
					dp[i][j] = dp[i+1][j-1]
				}
			}

			if dp[i][j] && j-i+1 > maxLen {
				maxLen = j-i+1
				res = s[i:j+1]
			}
		}
	}
	return res
}