创建网站需要什么,wordpress改动立马生效,网站个人备案需要什么资料,做广告推广哪个平台好一刷 给你一个字符串 s#xff0c;找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同#xff0c;则该字符串称为回文字符串。 思路#xff1a;
返回最长回文子串#xff0c;用maxl、maxr记录最长回文子串的起始和终点位置即可。
二维数组#xff0c;dp[i][j]…一刷 给你一个字符串 s找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同则该字符串称为回文字符串。 思路
返回最长回文子串用maxl、maxr记录最长回文子串的起始和终点位置即可。
二维数组dp[i][j]表示s[i:j1]是否是回文子串dp中可以选择记录当前子串最大长度也可以选择记录是否是回文子串因为代码中的扫描方式子串长度递增所以用maxl和maxr记录最新的回文子串即可二刷再改
二刷改进方向
1、dp数组初始化方式可以简化
2、不需要计算最大子串长度
class Solution:def longestPalindrome(self, s: str) - str:n len(s)maxl, maxr 0, 0res 1dp [[0]*n for i in range(n)]for i in range(n):dp[i][i] 1if n1:for i in range(n-1):if s[i] s[i1]:dp[i][i1] 2res 2maxl, maxr i, i1for i in range(2, n):for j in range(n-i):if s[j] s[ij] and dp[j1][ij-1]!0:dp[j][ij] dp[j1][ij-1] 2res max(res, dp[j][ij])maxl, maxr j, ijreturn s[maxl:maxr1]
