5. Longest Palindromic Substring

5. Longest Palindromic Substring

题目描述

 

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad" Output: "bab" Note: "aba" is also a valid answer.

Example:

Input: "cbbd" Output: "bb"

分析

本题要求找出字符串的最长回文子串，将结果分为两种情况：奇/偶数长度的字符串。挨个遍历字符串中的字符，将其作为对称中心，然后向字符串两端延展，看是否对称，最后取最大值。

在某个固定的索引起点开始，利用helper()函数，依次向两端延伸，找到距离最远的对称字符

def helper(self,s,l,r):    #l/r为回文字符串的左/右两个端点 while l>=0 and r<len(s) and s[l]==s[r]:    #若满足回文对称，左/右两个端点向两端继续延伸 l-=1;r+=1 return s[l+1:r]    #返回找到的最长回文字符串

主函数

def longestPalindrome(self, s): """ :type s: str :rtype: str """ ans='' #保存结果 s_len=len(s) if s_len in [0,1]: return s for i in xrange(s_len): #i为对称中心的索引 #奇数长度 odd=self.helper(s,i-1,i+1) if len(odd)>len(ans): #取当前最大值 ans=odd #偶数长度 even=self.helper(s,i,i+1) if len(even)>len(ans): #取当前最大值 ans=even return ans

第二次做：笨方法

class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ le = len(s) maxlen = 1 ans = "" if le == 0 else s[0] for i in range(le): l = r = i a = 1 # 奇数 while l > 0 and r < le - 1: r = r + 1 l = l - 1 if s[r] == s[l]: a = a+2 if a > maxlen: maxlen = a ans = s[l:r+1] else: break r = i l = i - 1 a = 0 # 偶数 while l >= 0 and r < le: if s[r] == s[l]: a = a+2 if a > maxlen: maxlen = a ans = s[l:r+1] r = r + 1 l = l - 1 else: break return ans