【Leetcode刷题】5. 最长回文子串

题目

描述

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

示例1

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

示例2

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

示例3

输入：s = "a"
输出："a"

示例4

输入：s = "ac"
输出："a"

提示

（1）1 <= s.length <= 1000

（2）s 仅由数字和英文字母（大写和/或小写）组成

解题思路

（1）使用动态规划算法寻找字符串中最长回文

（2）以字符串"abcdefedcdefaf"，生存dp矩阵，对角线为1，其余为0

（3）使用dp[i][j] 表示 s[i..j] 是否是回文串，其中j代表行，i代表列

（4）将不需要被循环到的dp[i][j]标红

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0
b	0	1	0	0	0	0	0	0	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	0	0	0	0	0	0	0	0
f	0	0	0	0	0	1	0	0	0	0	0	0	0	0
e	0	0	0	0	0	0	1	0	0	0	0	0	0	0
d	0	0	0	0	0	0	0	1	0	0	0	0	0	0
c	0	0	0	0	0	0	0	0	1	0	0	0	0	0
d	0	0	0	0	0	0	0	0	0	1	0	0	0	0
e	0	0	0	0	0	0	0	0	0	0	1	0	0	0
f	0	0	0	0	0	0	0	0	0	0	0	1	0	0
a	0	0	0	0	0	0	0	0	0	0	0	0	1	0
f	0	0	0	0	0	0	0	0	0	0	0	0	0	1

（5）第一行判断字符串"a"的最长回文，start = 0， max_len = 1

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0

（6）第二行判断字符串"ab"的最长回文，"a"!="b",  start = 0， max_len = 1

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0
b	0	1	0	0	0	0	0	0	0	0	0	0	0	0

（7）第三行判断字符串"abc"的最长回文，"a"!="c",  "b"!="c",  start = 0， max_len = 1

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0
b	0	1	0	0	0	0	0	0	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	0	0	0	0	0	0

（8）第四行判断字符串"abcd"的最长回文，"a"!="d",  "b"!="d",  "c"!="d", start = 0， max_len = 1

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0
b	0	1	0	0	0	0	0	0	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	0	0	0	0	0	0	0

（9）第五行判断字符串"abcde"的最长回文，"a"!="e",  "b"!="e",  "c"!="e", "d"!="e",start = 0， max_len = 1

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0
b	0	1	0	0	0	0	0	0	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	0	0	0	0	0	0	0	0

（10）第六行判断字符串"abcdef"的最长回文，"a"!="f",  "b"!="f",  "c"!="f", "d"!="f",, "e"!="f"，start = 0， max_len = 1

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0
b	0	1	0	0	0	0	0	0	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	0	0	0	0	0	0	0	0
f	0	0	0	0	0	1	0	0	0	0	0	0	0	0

（11）第七行判断字符串"abcdefe"的最长回文，"a"!="e",  "b"!="e",  "c"!="e", "d"!="e", "e"="e"，"f"!="e"，j-i = 2<=2,  dp[6][4] = 1, start = 4， max_len = 3, 最长回文为"efe"

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0
b	0	1	0	0	0	0	0	0	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	0	0	0	0	0	0	0	0
f	0	0	0	0	0	1	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	1	0	0	0	0	0	0	0

（12）第八行判断字符串"abcdefed"的最长回文，"a"!="d",  "b"!="d",  "c"!="d", "d"="d", "e"！="d"，"f"!="d"，"e"！="d"，j-i = 4 > 2,  并且dp[7-1][3+1] = 1, 所以 dp[7][3] = 1, start = 3， max_len = 5, 最长回文为"defed"

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0
b	0	1	0	0	0	0	0	0	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	0	0	0	0	0	0	0	0
f	0	0	0	0	0	1	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	1	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	1	0	0	0	0	0	0

（13）第九行判断字符串"abcdefedc"的最长回文，"a"!="c",  "b"!="c",  "c"="c", "d"!="c", "e"！="c"，"f"!="c"，"e"!="c"，"d"!="c"，j-i = 6 > 2,  并且dp[8-1][2+1] = 1, 所以 dp[8][2] = 1, start = 2， max_len = 7, 最长回文为"cdefedc"

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0
b	0	1	0	0	0	0	0	0	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	0	0	0	0	0	0	0	0
f	0	0	0	0	0	1	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	1	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	1	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	1	0	0	0	0	0

（14）第十行判断字符串"abcdefedcd"的最长回文，"a"!="d",  "b"!="d",  "c"="d", "d"="d",但dp[9-1][3+1] = 1，也就是e!=c，所以"defedcd"不能成为回文，因此继续往下进行比较，"e"！="d"，"f"!="d"，"e"!="d"，"d"="d"，"c"!="d"，j-i = 6 > 2,  并且dp[9-1][7+1] = 1, 所以 dp[9][7] = 1, 字符串“dcd”为回文，但是长度为3，小于max_len，因此strat与max_len不变。

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0
b	0	1	0	0	0	0	0	0	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	0	0	0	0	0	0	0	0
f	0	0	0	0	0	1	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	1	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	1	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	1	0	0	0	0	0
d	0	0	0	0	0	0	0	1	0	1	0	0	0	0

（15）同理继续往下进行检索，得到下面表格

	a	b	c	d	e	f	e	d	c	d	e	f	a	f
a	1	0	0	0	0	0	0	0	0	0	0	0	0	0
b	0	1	0	0	0	0	0	0	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	0	0	0	0	0	0	0	0
f	0	0	0	0	0	1	0	0	0	0	0	0	0	0
e	0	0	0	0	1	0	1	0	0	0	0	0	0	0
d	0	0	0	1	0	0	0	1	0	0	0	0	0	0
c	0	0	1	0	0	0	0	0	1	0	0	0	0	0
d	0	0	0	0	0	0	0	1	0	1	0	0	0	0
e	0	0	0	0	0	0	1	0	0	0	1	0	0	0
f	0	0	0	0	0	1	0	0	0	0	0	1	0	0
a	0	0	0	0	0	0	0	0	0	0	0	0	1	0
f	0	0	0	0	0	0	0	0	0	0	0	1	0	1

（16）最后得到最长字串为“cdefedc” 和 “fedcdef” ，长度为7

代码

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        # 特殊处理
        if size == 1:
            return s
        # 创建动态规划dynamic programing表
        dp = [[False for _ in range(size)] for _ in range(size)]
        # 初始长度为1，这样万一不存在回文，就返回第一个值（初始条件设置的时候一定要考虑输出）
        max_len = 1
        start = 0
        for j in range(1,size):
            for i in range(j):
                # 边界条件：
                # 只要头尾相等（s[i]==s[j]）就能返回True
                if j-i<=2:
                    if s[i]==s[j]:
                        dp[i][j] = True
                        cur_len = j-i+1
                # 状态转移方程 
                # 当前dp[i][j]状态：头尾相等（s[i]==s[j]）
                # 过去dp[i][j]状态：去掉头尾之后还是一个回文（dp[i+1][j-1] is True）
                else:
                    if s[i]==s[j] and dp[i+1][j-1]:
                        dp[i][j] = True
                        cur_len = j-i+1
                # 出现回文更新输出
                if dp[i][j]:
                    if cur_len > max_len:
                        max_len = cur_len
                        start = i

        return s[start:start+max_len]

总结

动态规划的核心思想就是 考虑最后一行的最优解与不考虑最后一行的最优解进行比较，取最优。

每一行代表新增一个字符，用第一个字符与新增的字符进行比较，“cdefedc” ，相等，则回溯前一行的dp[j-1][i+1]是否等于1，“defed”， 即前一行中新增字符时，是否形成回文。

Reference

题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台