Question:
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
给定一个字符串,找到其最长回文子串
Examples:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"
Solution:
方法一
找到所有子串后,在判断子串是否回文,但是看题目说字符长度为1000,这样的暴力解法的时间复杂度为o(n^3),附上暴力解法的代码,但是会提示 Time Limit Exceeded
Code:
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
Str = ''
Max = 0
for length in range(1,len(s)+1):
for i in range(len(s)-length+1):
j = i+length
if(self.reversedStr(s[i:j])):
if(Max<length):
Max = length
Str = s[i:j]
return Str
def reversedStr(self,s):
for i in range(len(s)):
if(s[i] != s[len(s)-i-1]):
return False
return True
方法二
动态规划解法
时间复杂度为o(n^2)
具体算法如下:
首先我们假设有字符串s,子串为s,start为子串s在s上的初始位置,end为子串s`在s上的结束位置
我们假设s[start:end]回文子串,那么s[start+1,end-1]必定也是回文子串就会存在公式.
因此我们用dp[start][end] = dp[start+1][end-1] and (s[start]与s[end]是否相等)
如果子串dp[start+1][end-1]为回文子串并且s[start]==s[end]的时候,说明dp[start][end]也是回文子串
而s中的单个字符与本身相等的,所以dp[i][i]也是回文子串
如果s[i]==s[i+1],dp[i][i+1]也是回文字串
因此我们的代码如下所示:
Code:
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
start = 0
MaxLength = 0
dp = [[False for i in range(len(s))] for i in range(len(s))]
if(len(s)==1):
return s
for i in range(len(s)):
dp[i][i] = True
if(i<len(s)-1 and s[i] == s[i+1]):
dp[i][i+1] = True
start = i
MaxLength = 2
for length in range(3,len(s)+1):
for i in range(len(s)-length+1):
j = i+length-1
if(s[j]==s[i] and dp[i+1][j-1]):
dp[i][j] = True
MaxLength = length
start = i
if(MaxLength>=2):
return s[start:start+MaxLength]
return s[0]
还有其他解法,比方说用某个字符为中心点往四周拓展看是否回文,时间复杂度为o(n^2),说还有一个(Manacher’s algorithm)时间复杂的o(n),还需要再看看
