本文主要是介绍9.最长回文子串-Leetcode 005（python），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 题目描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
- 示例
示例 1：
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
- 解决方案一
从字符串s的第一个字符开始遍历，判断往后的每一个字符串是否是回文子串，如果是的话，再比较该回文子串的长度与最长回文子串的长度。使用到了python的字符串切片操作，格式： [start:end:step]。
这种解法比较暴力，且费时。
- 代码
class Solution:def longestPalindrome(self, s):""":type s: str:rtype: str"""#如果字符串为空或者长度为1，则直接返原字符串if len(s) == 1 or not s:return s#记录最长回文子串的长度 maxlen = 0#记录最长回文子串的内容result = ''#从头开始遍历字符串sfor i in range(len(s)):#从当前记录的最大回文子串的长度往后开始遍历查看，因为如果长度小于maxlen的话，即使是回文子串，也不是最长的，不可能作为结果输出for j in range(maxlen,len(s) - i):#字符串切片操作str_ = s[i:i+j+1]_rts = str_[::-1]#判断是否是回文子串且最长if str_ == _rts and len(str_) > maxlen:maxlen = len(str_)result = str_return result- 解决方案二
中心枚举的思想，遍历每一个字符，从当前字符串开始，假设它是回文子串的中心，判断左右的字符是否相等。重点在于区分回文子串的长度是奇数和偶数两种情况。
- 代码二
class Solution:def longestPalindrome(self, s):""":type s: str:rtype: str"""l = len(s)maxlen = 0 result = ''for i in range(l):#中心枚举第一种情况：回文子串长度为奇数#从当前字符开始，判断它往前数第x个字符和往后数第x个字符是否相等x = 1while i-x>=0 and i+x <l:if s[i-x] == s[i+x]:x += 1else:breakx -= 1#更新maxlen和当前最长回文子串if(2*x+1)<=l and (2*x+1)>=maxlen:maxlen = 2*x+1result = s[i-x:i+x+1]#中心枚举第二种情况：回文子串长度为偶数#从当前字符串开始，判断它往前数第y个字符和往后数第y+1个字符#因为y从0开始，所以可以理解为判断当前字符和它往后数第1个，判断往前数第1个和往后数第2个，依次类推，即回文子串的中心在当前字符和它后一个字符的中间。y = 0while i-y>=0 and i+y+1 <l:if s[i-y] == s[i+y+1]:y += 1else:breaky -= 1#更新maxlen和当前最长回文子串if(2*y +2)<=l and (2*y+2)>=maxlen:maxlen = 2*y+2result = s[i-y:i+y+2]return result
这篇关于9.最长回文子串-Leetcode 005（python）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
