5 sous - chaîne palindrome la plus longue (intervalle DP)

1. Description du problème：

Je te donne une chaîne. s,Trouver s La plus longue chaîne de palindromes.

Exemple 1：

Entrée：s = "babad"
Produits："bab"
Explication："aba" C'est aussi la réponse à la question.

Exemple 2：

Entrée：s = "cbbd"
Produits："bb" 

Conseils：

1 <= s.length <= 1000
s Composé uniquement de chiffres et de lettres anglaises

Source:：Boucle de force（LeetCode）
Liens：https://leetcode.cn/problems/longest-palindromic-substring/

2. Analyse des idées：

Le sujet est similaire àSous - séquence palindrome la plus longueLa question de,Et la restriction de substrat exige que la chaîne soit continue,Mais c'est une idée similaire,Parce qu'il s'agit également de résoudre le problème de la satisfaction d'une limite dans un intervalle,Donc vous pouvez utiliser l'intervalle dp C'est réglé., C'est juste qu'il y a une différence dans le calcul de l'état , Juste un petit ajustement ,Pour une longueur de 1 Donc la longueur de la chaîne palindrome est   1;Pour une longueur de 2 Le jugement substratif de s[i] == s[j],égal à 2;Longueur supérieure à 2 Le jugement substratif de s[i] == s[j] Et f(i + 1,j - 1) Plus grand que 0 Description s[i + 1:j - 1] C'est la chaîne palindrome .

3. Les codes sont les suivants:：

python（Temps mort）：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        f = [[0] * (n + 10) for i in range(n + 10)]
        res = ""
        #  Intervalle classique dpCadre, Longueur de l'énumération
        for l in range(1, n + 1):
            # Début de l'énumérationi
            i = 0
            while i + l - 1 < n:
                # j Le point de départ actuel est iLa longueur estl Fin de l'intervalle de 
                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
}