求解最长回文子串

题目描述

给定一个字符串s，找出s中最长的回文子串。可以假设s的最大长度为1000。
例一：输入：”babad“ 输出：”bab“(或者”aba“)
例二：输入：”cbbd“ 输出：”bb“

解题方法

方法一：在刚看到这道题目的时候很多人包括我自己本人想到的第一种方法就是遍历出所有的情况然后再判断每种情况是不是回文子串

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length=len(s)
        if length<=1:
            return s
        maxlen=1
        index=0
        for i in range(length):
            for j in range(i+1,length+1):
                flag = True
                temp=s[i:j]
                length1=len(temp)
                for m in range(length1):
                    if temp[m]!=temp[length1-m-1]:
                        flag=False
                if flag:
                    if maxlen<j-i:
                        index=i
                        maxlen=j-i
        return s[index:index+maxlen]

算法时间复杂度分析;首先我们遍历出所有的子串情况需要O(n2),然后我们在判断该子串是不是回文子串又需要O(n)，所以总的时间复杂度需要O(n3)

那么基于以上的方式我们能不能有所改进，经我们分析可得造成方法一求解时间复杂度过大的一个原因就是我们重复计算了已经确定了是回文子串的某个子串，比如说我们已经知道”bab“是回文子串，那么“bbabb”不过是在“bab”的两边各加上一个“b”,所以我们可以在方法一的基础上进行改进-----即使用动态规划

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length=len(s)
        dp=[([0])*length for _ in range(length)]
        if length<=1:
            return s
        max,start=1,0
        for i in range(length):
            dp[i][i]=1
            if i<length-1:
               if s[i]==s[i+1]:
                    dp[i][i+1]=1
                    max=2
                    start=i
        for l in range(3,length+1):
            for i in range(length-l+1):
                j=i+l-1
                if s[i]==s[j]:
                    if dp[i+1][j-1]==1:
                        dp[i][j]=1
                        max=l
                        start=i
        return s[start:start+max]

算法时间复杂度分析 ：由于我们只需要在遍历出3–length种长度的子串，不需要再对子串进行从头到尾的判断，所以时间复杂度为O(n2),但是我们使用了O(n2)的空间来存储相应的状态。