python最长回文子串leetcode_Python版LeetCode5. 最长回文子串

本文转载自【微信公众号：机器学习算法与Python精研，ID:AITop100】经微信公众号授权转载，如需转载与原文作者联系

题目：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入 "babad"输出 "bab"注意 "aba"也是一个有效答案。

示例 2：

输入 "cbbd"输出 "bb"

思路：

以每个位置的元素为中心轴进行两边扩展(只有两边对称相同时就会继续向两边延伸)，比较，保存取最大长度。

参考代码：

classSolution:deflongestPalindrome(self, s):""" :type s: str :rtype: str """ left = right = n = len(s)for i in range(n - 1):if2 * (n - i) + 1 < right - left + 1:break l = r = iwhile l >= and r < n and s[l] == s[r]: l -= 1 r += 1if r - l - 2 > right - left: left = l + 1 right = r - 1 l = i r = i + 1while l >= and r < n and s[l] == s[r]: l -= 1 r += 1if r - l - 2 > right - left: left = l + 1 right = r - 1return s[left:right + 1]

总结

以上是生活随笔为你收集整理的python最长回文子串leetcode_Python版LeetCode5. 最长回文子串的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。