博客

描述


给定一个仅包含小写字母的字符串，求它的最长回文子串的长度。

所谓回文串，指左右对称的字符串。

所谓子串，指一个字符串删掉其部分前缀和后缀（也可以不删）的字符串

数据范围：字符串长度1≤s≤350

进阶：时间复杂度：O(n) ，空间复杂度：O(n)

输入描述：

输入一个仅包含小写字母的字符串

输出描述：

返回最长回文子串的长度

示例1


输入：

cdabbacc

输出：

4

说明：

abba为最长的回文子串

方法一：动态规划


dp[i][j]表示s[i:j+1]是否为回文子串

if dp[i+1][j-1] == True and s[i] == s[j]:

dp[i][j] = True

else:

dp[i][j] = False

时间复杂度n^2 空间复杂度n

def fun(s):
    n = len(s)
    dp = [0]*n
    re = 0 
    for i in range(n-1,-1,-1):
        for j in range(n-1,i-1,-1):
            if i==j:
                dp[j] = 1
            elif i+1 == j:
                if s[i] == s[j]:
                    dp[j] = 2
                else:
                    dp[j] = 0
            else:
                if s[i]==s[j] and dp[j-1] != 0:
                    dp[j] = dp[j-1]+2
                else:
                    dp[j] = 0
        re = max(re,max(dp))
    return re
s = input()
print(fun(s))

方法二：中心扩散法


时间复杂度n^2

def g(s):
    n = len(s)
    re=0
    for i in range(n):
    	#情形1子串为奇数
        left,right = i,i
        while left>=0 and right<n and s[left]==s[right]:
            left -= 1
            right += 1
        re = max(re,right-left-1)
        #情形2子串为偶数
        if i>1 and s[i] == s[i-1]:
            left,right = i-1,i
            while left>=0 and right<n and s[left]==s[right]:
                left -= 1
                right += 1
            re = max(re,right-left-1)
    return re
print(g('cdabbacc'))