Longest Palindromic Substring

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),还需要再看看