转载

最长回文子串

最长回文子串

题目

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

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

分析

? 可以用动态规划来做,复杂度为 O ( n 2 ) O(n^2) ,复杂度太高,以后改进!

通过分析我们可以知道,长度为1的子字符串,是回文,长度为2的子字符串,如果两个字符相等

是回文串,长度大于2的子字符串,满足下面的递推公式
B ( m , n ) = B ( m + 1 , n ? 1 )           s m = = s n B ( m , n ) = f a l s e           s m s n B(m,n)=B(m+1,n-1) \ \ \ \ \ \ \ \ \ s_m==s_n \\ B(m,n)= false \ \ \ \ \ \ \ \ \ s_m \neq s_n
B(m,n)代表 s m , s m + 1 , . . . s n s_m, s_{m+1}, ...s_n 是否是回文串

python代码

class Solution:
    def longestPalindrome(self, s):
        """ :type s: str :rtype: str """
        if s == "": return ""
        n = len(s)
        
        
        dp = [[0 for i in range(0, n+1)] for i in range(0, n+1)]
        
        for i in range(1, n+1): dp[i][i] = 1
            
        
        for x in range(1, n):
            for i in range(1, n-x+1):
                j = i + x
                if j-i == 1:
                    if s[i-1] == s[j-1]:
                        dp[i][j] = 1
                else:
                    if s[i-1] == s[j-1]:
                        dp[i][j] = dp[i+1][j-1]
                    else:
                        dp[i][j] = 0
                        
        for x in range(0, n)[::-1]:
            for i in range(1, n-x+1):
                j = i + x
                if dp[i][j] == 1:
                    return s[i-1:j]
        
正文到此结束
本文目录