最长回文子串(python)多种解法

题目：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：
输入: “cbbd”
输出: “bb”

解法一:
暴力解法，列出所有子字符串，判断其是否为回文子串，并保留最长回文子串。
(时间超出leetcode的时间限制ahhhhh)

array1=list(i for i in input().split())#array2=list(i for i in input().split())def isPalindromic(s):if len(s)==1:return Trueelse:for i in range(len(s)//2):if s[i]!=s[len(s)-1-i]:return Falsereturn Truemax_len=0max_Palindrome_str=""max_Palindrome=[]for i in range(len(s)):for j in range(i,len(s)):if isPalindromic(s[i:j+1])==True:if len(s[i:j+1])>max_len:max_len=len(s[i:j+1])max_Palindrome=s[i:j+1]#print(max_Palindrome)for i in range(len(max_Palindrome)):max_Palindrome_str=max_Palindrome_str+max_Palindrome[i]return max_Palindrome_strprint(longestPalindrome(array1))

时间复杂度：两层 for 循环 O(n²），for 循环里边判断是否为回文 O(n），所以时间复杂度为 O(n³）。
空间复杂度：O(1），常数个变量。

解法二：
最长公共子串法(1)，找出该字符串和反转的字符串公共部分，并且看对应下标是否一致。

array1=list(i for i in input().split())def longestPalindrome(s):if s==None:return ""s_reverse=list(reversed(s))length=len(s)max_len=0max_end=0a = [[0] * length for x in range(length)]  #len长len列for i in range(length):for j in range(length):if s[i]==s_reverse[j]:if i==0 or j==0:a[i][j]=1else:a[i][j]=a[i-1][j-1]+1if a[i][j]>max_len and length-1-j+a[i][j]-1==i:#j对应翻转前的位置再加上最大回文子串长度是否等于imax_len=a[i][j]max_end=ireturn s[max_end-max_len+1:max_end+1]
print(longestPalindrome(array1))

时间复杂度 O(n²)。
空间复杂度降为 O(n²)。
执行用时5696 ms
内存消耗38.9 MB

解法三 ：
最长公共子串法优化(2)

array1=list(i for i in input().split())def longestPalindrome(s):if s==None:return ""s_reverse=list(reversed(s))length=len(s)max_len=0max_end=0a = [0] * lengthfor i in range(length):for j in range(length-1,-1,-1):#注意:要倒过来,因为正过来时，需要的上一轮的数据被这一轮数据更新了if s[i]==s_reverse[j]:if i==0 or j==0:a[j]=1else:a[j]=a[j-1]+1else:a[j]=0if a[j]>max_len and length-1-j+a[j]-1==i:#j对应翻转前的位置再加上最大回文子串长度是否等于imax_len=a[j]max_end=ireturn s[max_end-max_len+1:max_end+1]
print(longestPalindrome(array1))

时间复杂度 O(n²)。
空间复杂度降为 O(n)。
执行用时 5068 ms
内存消耗 13.7 MB

解法四：暴力破解优化（1）

array1=list(i for i in input().split())def longestPalindrome(s):length=len(s)max_len=0max_Palindrome=[]max_Palindrome_str=""p=[[0]*length for x in range(length)]if  length==0:return  ""for lenh in range(1,length+1):for start in range(length):end=start+lenh-1if end>=length:breakp[start][end] = (lenh == 1 or lenh == 2 or p[start + 1][end - 1]) and s[start] == s[end]if p[start][end] and lenh > max_len:max_len = lenhmax_Palindrome = s[start:end + 1]for i in range(len(max_Palindrome)):max_Palindrome_str = max_Palindrome_str + max_Palindrome[i]return max_Palindrome_str
"""if lenh == 1:p[start][end] = Trueelif lenh == 2:if s[start] == s[end]:p[start][end] = Trueelse:if s[start] == s[end]  and p[start + 1][end - 1]==True:p[start][end] = True
"""
print(longestPalindrome(array1))

时间复杂度：两层循环 O(n²）。
空间复杂度：用二维数组 P 保存每个子串的情况 O(n²)。
执行用时 4716ms
内存消耗 21.4 MB

解法五：暴力破解优化（2）

array1=list(i for i in input().split())def longestPalindrome(s):length=len(s)max_len=0res=[]res_str=""a=[[0]*length for _ in range(length)]for i in range(length-1,-1,-1):#注：倒序，因为不像上一种方法，已有初始值。for j in range(i,length):a[i][j]=(j-i<2 or a[i+1][j-1]) and s[i]==s[j]#j-i为两者间距离if a[i][j] and j-i+1>max_len:max_len=j-i+1res=s[i:j+1]for i in range(len(res)):res_str=res_str+res[i]return res_strprint(longestPalindrome(array1))

时间复杂度：两层循环 O(n²）。
空间复杂度：用二维数组 a 保存每个子串的情况 O(n²)。
执行用时 4364 ms
内存消耗 21.5 MB

解法五：暴力破解优化之优化（2）

array1=list(i for i in input().split())def longestPalindrome(s):length=len(s)max_len=0res=[]res_str=""a=[[0]*length for _ in range(length)]for i in range(length-1,-1,-1):#注：倒序，因为不像上一种方法，已有初始值。for j in range(length-1,i-1,-1):a[j]=(j-i<2 or a[j-1]) and s[i]==s[j]#j-i为两者间距离if a[j] and j-i+1>max_len:max_len=j-i+1res=s[i:j+1]for i in range(len(res)):res_str=res_str+res[i]return res_strprint(longestPalindrome(array1))

时间复杂度：两层循环 O(n²）。
空间复杂度： O(n)。
执行用时 3060 ms
内存消耗21.6 MB

解法六:中心扩展法

array1=list(i for i in input().split())
print(array1)#array2=list(i for i in input().split())def expandAroundCenter(s,i,j):"""找出回文子串，返回其长度"""L,R=i,jwhile(L>=0 and R<len(s) and s[L]==s[R]):L-=1R+=1return R-L-1def longestPalindrome(s):if s==None:return Noneelse:start=0end=0for i in range(len(s)):len1=expandAroundCenter(s,i,i)len2=expandAroundCenter(s,i,i+1)len3=max(len1,len2)if len3>end-start:start=i-(len3-1)//2end=i+len3//2return s[start:end+1]print(longestPalindrome(array1))

时间复杂度：O(n²）。
空间复杂度：O(1)。
执行用时1276ms
内存消耗13.8 MB

解法七: Manacher’s Algorithm 马拉车算法。

扩展：

反转列表的三种方法

print("====第一种====")
a=[1,2,3,4,5]
a.reverse()
print(a)print("====第二种====")
b=[1,2,3,4,5]
b_reverse=list(reversed(b))
print(b_reverse)print("====第三种====")
c=[1,2,3,4,5]
c_reverse=c[::-1]
print(c_reverse)

输出：

====第一种====
[5, 4, 3, 2, 1]
====第二种====
[5, 4, 3, 2, 1]
====第三种====
[5, 4, 3, 2, 1]

二维数组赋值问题

m=5,n=6
a=[[0]*n]*m

上述代码为生成一个m行n列的矩阵，但需要注意的是，当改变其中一个值时，该值所在列都会被改变。
欲使其独立变化，则需要初始化如下：

a=[[0]*n for _ in range(m)]