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

【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]标红

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

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

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

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

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

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

（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"

（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"

（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"

（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不变。

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

（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 = 1start = 0for j in range(1,size):for i in range(j):# 边界条件：# 只要头尾相等（s[i]==s[j]）就能返回Trueif j-i<=2:if s[i]==s[j]:dp[i][j] = Truecur_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] = Truecur_len = j-i+1# 出现回文更新输出if dp[i][j]:if cur_len > max_len:max_len = cur_lenstart = ireturn s[start:start+max_len]

总结

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

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

Reference

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