Longest Palindromic Substring

medium, Array/String

Question:

给定字符串s, 返回最长回文子字符串

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

Input: "cbbd"
Output: "bb"

Solution

抓住回文关于中心对称的特点（中心可能在两个字母之间)

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        start, end = 0, 0

        for i in xrange(len(s)):
            len1 = self.expandAroundCenter(s, i, i)
            len2 = self.expandAroundCenter(s, i, i+1)
            maxlen = max(len1,len2)
            if maxlen > end-start:
                start = i - (maxlen-1)/2
                end = i+maxlen/2
        return s[start:end+1]
    
    def expandAroundCenter(self, s, left, right):
        L, R = left, right
        while (L>=0 and R < len(s) and s[L]==s[R]):
            L-=1
            R+=1            
        return R-L-1