python求字符串最长子串_Python刷题:最长回文子串(字符串)

Love The Way You Lie 2022-11-01 00:47 108阅读 0赞

题目描述

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

解题思路

当字符串不为空时,回文子串最少也是一个字符,即初始长度为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)

总结

关于回文的题目在各种试题中也常常见,当然也比较简单,但是一般的解法通常会含有两个循环,相对于上面的算法只用了一个循环,显然上面的算法更好。

题目及解题算法来自:最长回文子串

发表评论

表情:
评论列表 (有 0 条评论,108人围观)

还没有评论,来说两句吧...

相关阅读

    相关

    / 最长回文子串 输入一个字符串s,请找出s中最长回文子串的长度 dp[i][j]是子串s[i...j]中的最长回文子串的长度 / public clas

    相关

    回文串指给定的字符串,正着读和反着读都是一样的。如ADA,反过来还是ADA即为回文串。最长回文子串指查找一给定字符串中最长的回文串。 通常有以下4种解法。主要考虑的是时间复杂

    相关

    【题目】 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 输入: “babad” 输出: “bab” 注意: “aba”