leetcode5. Longest Palindromic S

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"

Note:
---
1. 递归失败，主要原因字符串太大时候空间复杂度太高，导致 Time Limit Exceeded
2. 判断是否回文：两边向中心扩展、中心向两边扩展，中心向两边扩展更节省空间

# 采用递归，无法 AC，原因 Time Limit Exceeded
class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def isPalindrome(s,i,j):
            if i>=len(s) or j<0:
                return False
            elif i==j or i==(j+1):
                return True
            elif s[i] == s[j]:
                return isPalindrome(s,i+1,j-1)

        start = 0
        end = 0
        for i in range(len(s)):
            for j in range(len(s)-1,i,-1):
                if(isPalindrome(s,i,j)):
                    if (j-i)>(end-start):
                        start = i
                        end = j
        return s[start:end+1]

# 中心向外扩展
class Solution:
    def longestPalindrome(self, s):
        res = ""
        for i in range(len(s)):
            # odd case, like "aba"
            tmp = self.helper(s, i, i)
            if len(tmp) > len(res):
                res = tmp
            # even case, like "abba"
            tmp = self.helper(s, i, i + 1)
            if len(tmp) > len(res):
                res = tmp
        return res

    # get the longest palindrome, l, r are the middle indexes
    # from inner to outer
    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]