做云购网站,佛山顺德网站制作公司哪家好,网站模糊背景,网站建设跟加入会员哪个效果好leetcode 5 最长回文子串给定一个字符串 s#xff0c;找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1#xff1a;输入: babad
输出: bab
注意: aba 也是一个有效答案。示例 2#xff1a;输入: cbbd
输出…leetcode 5 最长回文子串给定一个字符串 s找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1输入: babad
输出: bab
注意: aba 也是一个有效答案。
示例 2输入: cbbd
输出: bb思路动态规划为了改进暴力法我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑 这个示例。如果我们已经知道 是回文那么很明显 一定是回文因为它的左首字母和右尾字母是相同的。我们给出 的定义如下因此基本示例如下这产生了一个直观的动态规划解法我们首先初始化一字母和二字母的回文然后找到所有三字母回文并依此类推…复杂度分析时间复杂度O(n^2)O(n2)这里给出我们的运行时间复杂度为 O(n^2)O(n2) 。空间复杂度O(n^2)O(n2)该方法使用 O(n^2)O(n2) 的空间来存储表。具体写码的时候用一个变量代码中的sub来记录目前最长的子串长度用一个list代码中的max_len来记录最长子串的坐标另一个leetcode上速度比较快的算法有点类似滑动窗口法维护一个最大长度为lenth的窗口并使用python语法糖q q[::-1]来判断是否是回文字符串但是要注意的是维护窗口时要同时维护奇数和偶数两种窗口。答案class Solution(object):def longestPalindrome(self, s)::type s: str:rtype: strn len(s)if n 0:return if n 1:return sres [[0 for _ in range(n)] for _ in range(n)]sub 1max_len [0,0]for i in range(n):res[i][i] 1if i ! n-1 and s[i] s[i1]:res[i][i1] 1sub 2max_len[i,i1]for i in range(n):for j in range(1,min(i,n-i)1):if i-j0 and ijn and res[i-j1][ij-1] and s[i-j]s[ij]:res[i-j][ij] 1#print 12*jif sub12*j:sub 12*jmax_len [i-j,ij]#print sub,max_lenif i-j0 and i1jn and res[i-j1][ij] and s[i-j] s[ij1]:res[i-j][ij1] 1if sub22*j:sub 12*jmax_len [i-j,ij1]#print sub,max_lenreturn s[max_len[0]:(max_len[1]1)]class Solution(object):def longestPalindrome(self, s)::type s: str:rtype: strif len(s) 1 or s s[::-1]:return sstart 0length 1for i in range(len(s)):p s[i-length-1:i1]q s[i-length:i1]if i-length-1 0 and p p[::-1]:start i-length-1length 2if i-length 0 and q q[::-1]:start i - lengthlength 1return s[start:startlength][647] 回文子串给定一个字符串你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被计为是不同的子串。示例 1:输入: abc输出: 3解释: 三个回文子串: a, b, c.示例 2:输入: aaa输出: 6说明: 6个回文子串: a, a, a, aa, aa, aaa.注意:输入的字符串长度不会超过1000。思路这道题的动态规划思路跟上一道题第五题完全一样只不过在具体代码的时候使用一个变量来记录回文子串的个数。[516] 最长回文子序列给定一个字符串s找到其中最长的回文子序列。可以假设s的最大长度为1000。示例 1:输入:bbbab输出:4一个可能的最长回文子序列为 bbbb。示例 2:输入:cbbd输出:2一个可能的最长回文子序列为 bb。思路这道题跟上两道题的动态规划思路完全不一样首先这道题寻找的是最长回文子序列子序列可以不相连。其次这道题要返回的是最长回文子序列的长度不关心子序列所以构造动态规划数组时也稍有不同。具体来说引入 ,表示第i个字符至第j个字符组成的子串中最长回文子序列的长度。递推公式可以表示为注意在具体代码的时候循环应该是先判断间隔距离为1的所有字符对然后依次增加。答案class Solution(object):def longestPalindromeSubseq(self, s)::type s: str:rtype: intn len(s)if n1:return nif n2:if s[0]s[1]:return 2else:return 1resgrid [[0 for _ in range(n)] for _ in range(n)]for i in range(n):resgrid[i][i]1for gap in range(1,n):for i in range(n):if igapn:breakl ih igapif s[l]s[h]:resgrid[l][h] resgrid[l1][h-1]2else:resgrid[l][h]max(resgrid[l1][h],resgrid[l][h-1])return resgrid[0][n-1]
