今天做一道最長回文子串問題

Given a string?s, find the longest palindromic substring in?s. You may assume that the maximum length of?s?is 1000.

給定字符串s,找到其最長回文子串并輸出

回文定義為:字符串s與s的反轉s`完全相等

Example:

Input: "babad"Output: "bab"Note: "aba" is also a valid answer.

Example:

Input: "cbbd"Output: "bb"

思路一:
找到所有子串后,在判斷子串是否回文,但是看題目說字符長度為1000,這樣的暴力解法的時間復雜度為o(n^3),附上暴力解法的代碼,但是會提示 Time Limit Exceeded

1 class Solution(object): 2 def longestPalindrome(self, s): 3 """ 4 :type s: str 5 :rtype: str 6 """ 7 Str = '' 8 Max = 0 9 for length in range(1,len(s)+1): 10 for i in range(len(s)-length+1): 11 j = i+length 12 if(self.reversedStr(s[i:j])): 13 if(Max<length): 14 Max = length 15 Str = s[i:j] 16 17 return Str 18 def reversedStr(self,s): 19 for i in range(len(s)): 20 if(s[i] != s[len(s)-i-1]): 21 return False 22 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]也是回文字串
因此我們的代碼如下所示:

1 class Solution(object): 2 def longestPalindrome(self, s): 3 """ 4 :type s: str 5 :rtype: str 6 """ 7 start = 0 8 MaxLength = 0 9 dp = [[False for i in range(len(s))] for i in range(len(s))] 10 if(len(s)==1): 11 return s 12 for i in range(len(s)): 13 dp[i][i] = True 14 if(i<len(s)-1 and s[i] == s[i+1]): 15 dp[i][i+1] = True 16 start = i 17 MaxLength = 2 18 for length in range(3,len(s)+1): 19 for i in range(len(s)-length+1): 20 j = i+length-1 21 if(s[j]==s[i] and dp[i+1][j-1]): 22 dp[i][j] = True 23 MaxLength = length 24 start = i 25 if(MaxLength>=2): 26 return s[start:start+MaxLength] 27 return s[0]

還有其他解法,比方說用某個字符為中心點往四周拓展看是否回文,時間復雜度為o(n^2),說還有一個(Manacher’s algorithm)時間復雜的o(n),還需要再看看

轉載于:https://www.cnblogs.com/fzy0331-leetcodestudy/p/8328958.html

總結

以上是生活随笔為你收集整理的Longest Palindromic Substring的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。