Længste palindromiske delsekvens og delstreng

Vi udfylder LPS-tabellen i stigende intervallængde, efter samme mønster som generel interval-DP. For hvert interval [i, j] med længde 2 eller mere kontrollerer vi, om de to grænsetegn er ens, og anvender rekurrensformlen. Det endelige svar er dp[0][n-1], LPS for hele strengen.

Et elegant alternativ: LPS for strengen s er lig med LCS for s og dens omvendte streng s[::-1]. Det skyldes, at enhver palindromisk delsekvens i s er en fælles delsekvens for s og dens omvendte streng. Denne omskrivning giver dig mulighed for at genbruge din LCS-implementering direkte. Den omvendte version af 'bbbab' er 'babbb', og deres LCS er 4.

Den længste palindromiske delstreng kræver sammenhængende tegn. En brute force-tilgang kontrollerer alle O(n²) delstrenge og verificerer hver af dem i O(n)-tid — O(n³) i alt. Der findes to hurtigere tilgange: interval-DP i O(n²)-tid og med O(n²)-pladsforbrug samt udvidelse omkring centrum i O(n²)-tid, men med O(1)-pladsforbrug. Til interviews foretrækkes udvidelse omkring centrum, fordi den har en mindre konstant faktor og renere kode.

Definér dp[i][j] = True, hvis s[i..j] er et palindrom. Rekurrensformel: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Basistilfælde: dp[i][i] = True og dp[i][i+1] = (s[i] == s[i+1]). Hold styr på det længste fundne palindrom. Udfyld tabellen i stigende længderækkefølge. Det kører i O(n²)-tid og bruger O(n²)-plads.

Tilgangen med udvidelse omkring centrum prøver hvert tegn (samt hvert par af tilstødende tegn) som et muligt palindromcentrum og udvider udad, så længe begge sider matcher. Der er 2n-1 mulige centre (n for ulige længder og n-1 for lige længder). Hver udvidelse tager højst O(n)-tid, hvilket giver O(n²) i alt med O(1)-pladsforbrug — optimalt i de fleste interviewsituationer.

Interval-DP for LPS bruger O(n²)-plads. Når du kun har brug for længden (og ikke den faktiske delsekvens), kan du reducere pladsforbruget ved at bemærke, at dp[i][j] kun afhænger af dp[i+1][j-1], dp[i+1][j] og dp[i][j-1]. Ved at genbruge rækker og gemme én diagonalværdi kan du opnå O(n)-plads — implementeringen bliver dog mere kompleks, og det er sjældent nødvendigt i interviews.

Hvis du vil genskabe den faktiske palindromiske delsekvens, skal du spore tilbage gennem DP-tabellen. Start ved (0, n-1). Hvis s[i] == s[j], skal du føje tegnet til begge ender af dit resultat og gå til (i+1, j-1). Ellers skal du gå til den af (i+1, j) og (i, j-1), der har den største værdi. Denne grådige tilbagesporing genskaber entydigt én optimal palindromisk delsekvens.

Både LPS via interval-DP og LCS kører i O(n²)-tid og bruger O(n²)-plads. Udvidelse omkring centrum for den længste palindromiske delstreng bruger O(n²)-tid, men kun O(1)-plads. Manachers algoritme løser delstrengsproblemet i O(n)-tid og med O(n)-plads, men den er så kompleks, at interviewere sjældent forventer den. I de fleste interviewsituationer er udvidelse omkring centrum den forventede optimale løsning på delstrengsvarianten.

Vær opmærksom på disse faldgruber: (1) at forveksle subsekvens med delstreng — det er forskellige problemer med forskellige løsninger; (2) basistilfældet i interval-DP'en for intervaller af længde 2 kræver særskilt håndtering, eftersom dp[i+1][j-1] ville være dp[i+1][i] (et tomt interval); (3) ved udvidelse omkring centrum skal du initialisere max_len = 1 (hvert enkelt tegn er et palindrom); og (4) når du udtrækker resultatet, skal du beregne start = i - (best-1)//2 for korrekt at finde startindekset ud fra centrum.

I denne lektion lærte du: LPS bruger interval-DP med rekurrensen dp[i][j] = dp[i+1][j-1]+2, når tegnene matcher, den længste palindromiske delstreng løses bedst med udvidelse omkring centrum i O(n²)-tid og med O(1)-pladsforbrug, og LPS er lig med LCS for strengen og dens omvendte streng. Næste emne er palindromopdeling II, hvor en palindromtabel kombineres med 1D-DP for at finde det mindste antal snit.