题目
给你一个字符串 s
,找到 s
中最长的回文子串的长度。回文串是指从左读和从右读都一样的字符串,例如abcba
,abccba
例子
longestPalindrome('babad') -> 3
longestPalindrome('cbbd') -> 2
longestPalindrome('a') -> 1
假设
- 输入的参数不为空
tips
- 动态规划
答案
解法1
def longestPalindrome(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
ans = ""
# 枚举子串的长度 l+1
for l in range(n):
# 枚举子串的起始位置 i,这样可以通过 j=i+l 得到子串的结束位置
for i in range(n):
j = i + l
if j >= len(s):
break
if l == 0:
dp[i][j] = True
elif l == 1:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
if dp[i][j] and l + 1 > len(ans):
ans = s[i:j+1]
return len(ans)
性能:
- 时间复杂度
O(n^2)
- 空间复杂度
O(n^2)
关键点:
- 动态规划