5. Longest Palindromic Substring

Longest Palindromic Substring

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

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

Example 2:
Input: "cbbd"
Output: "bb"

思路：

1. 循环遍历每一个字符
2. 以每一个字符为中心向两边+1判断是否是回文字符串
3. 区分奇偶的两种情况（具体见上面两个例子）

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        res = ""
        for i in range(len(s)):
            tmp=self.helper(s,i,i)
            if len(tmp)>=len(res):
                res=tmp
            tmp=self.helper(s,i,i+1)
            if len(tmp)>=len(res):
                res=tmp
        return res

    def helper(self,s,l,r):
        while l>=0 and r<len(s) and s[l]==s[r]:
            l-=1
            r+=1
        return s[l+1:r]