5 longest palindrome substring (interval DP)

1. Problem description ：

Give you a string s, find s The longest palindrome substring in .

Example 1：

Input ：s = "babad"
Output ："bab"
explain ："aba" It's the same answer .

Example 2：

Input ：s = "cbbd"
Output ："bb" 

Tips ：

1 <= s.length <= 1000
s It consists only of numbers and English letters

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/longest-palindromic-substring/

2. Thought analysis ：

This topic is similar to The longest palindrome subsequence The problem of , The substring restriction requires that the string be continuous , But it's a similar idea , Because it is also a problem of solving a certain limit in an interval , So you can use intervals dp To solve , It's just that there are some differences in state calculation , Just a little adjustment , For length is 1 The length of the palindrome string is   1; For length is 2 Substring judgment of s[i] == s[j], Equal is 2; Longer than 2 Substring judgment of s[i] == s[j] also f(i + 1,j - 1) Greater than 0 explain s[i + 1:j - 1] Is the palindrome string .

3. The code is as follows ：

python（ Overtime ）：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        f = [[0] * (n + 10) for i in range(n + 10)]
        res = ""
        #  Classical interval dp frame ,  Enumeration length 
        for l in range(1, n + 1):
            #  Enumeration starting point i
            i = 0
            while i + l - 1 < n:
                # j The current starting point is i The length is l The end of the interval 
                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
}