题解 | #最长回文子串#
最长回文子串
https://www.nowcoder.com/practice/12e081cd10ee4794a2bd70c7d68f5507
#用dp数组存储了 较小长度回文串的数据 较大的直接在较短的上面继续增加 所以少了一层循环
s = input()
maxlen = 0
ls = len(s)
dp = [[0]*len(s) for _ in range(len(s))]
# 长度为1的回文串
for i in range(ls):
dp[i][i] = 1
maxlen = 1
# 长度为2的回文串
for i in range(ls-1):
if s[i] == s[i+1]:
dp[i][i+1] = 1
maxlen = 2
# 长度为l的回文串
for L in range(3,ls+1):
find_flag = False
for i in range(ls-L+1):
j = i+L-1
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1]
# 存在长为L回文串
if dp[i][j] == 1:
find_flag = True
maxlen =L
print(maxlen)
查看18道真题和解析