003.最长回文子串

• 5.最长回文子串
  • 贪心（错误）
  • 其他解法

最长回文子串 - 贪心（错误）

贪心是错的！缺少考虑 anana 的情况

func longestPalindrome(s string) string {
	n := len(s)
	if n == 0 {
		return ""
	}
	start := 0
	maxLen := 1
 
	// dp[i]: 以 i 结尾的最长回文子串长度
	dp := make([]int, n)
	// equal[i]: 以 i 结尾的最长回文子串的内容是否是同一字符
	equal := make([]bool, n)
	for i := range dp {
		dp[i] = 1
	}
 
	for i := 1; i < n; i++ {
		if s[i] == s[i - 1] {
			if equal[i - 1] {
				dp[i] = dp[i - 1] + 1
			} else {
				dp[i] = 2
			}
			equal[i] = true
		}
		if i - dp[i - 1] - 1 >= 0 && s[i] == s[i - dp[i - 1] - 1] {
			if dp[i - 1] + 2 > dp[i] {
				dp[i] = dp[i - 1] + 2
				equal[i] = false
			}
		}
		if dp[i] > maxLen {
			maxLen = dp[i]
			start = i - dp[i] + 1
		}
	}
 
	return s[start:start + maxLen]
}