Python刷题：最长回文子串（字符串）

Z时代
2024-01-10
分类：综合

Python刷题：最长回文子串（字符串）[Python基础]

题目描述

给定一个仅包含小写字母的字符串，求它的最长回文子串的长度。所谓回文串，指左右对称的字符串。

解题思路

当字符串不为空时，回文子串最少也是一个字符，即初始长度为1，当回文子串更长时，就可能有两种情况：例如“...aa...”或“...aba...”，即长度+1或+2。以后遍历时每增加一个字符，且该字符也包含在回文子串中时，就可以使用之前得到的最长的长度作为初始长度，按照+1或+2的逻辑进行判断了。

解题代码

s = "abcba"
if len(s) == 1:
    print(1)
elif s == s[::-1]:
    print(len(s))
else:
    # 初始长度为1
    max_len = 1
    # 从第二个字符开始判断
    for i in range(1, len(s)):
        # 长度+2的逻辑
        if i - max_len - 1 >= 0 and s[i - max_len - 1:i + 1] == s[i - max_len - 1:i + 1][::-1]:
            max_len += 2
        # 长度+1的逻辑
        elif i - max_len >= 0 and s[i - max_len:i + 1] == s[i - max_len:i + 1][::-1]:
            max_len += 1
    print(max_len)