5. 最长回文子串

思路

首先判断字符串是否是回文，是则直接返回，不是则遍历:

从第一个字符开始遍历，判断对应字符串是否是回文且是不是最大长度
时间复杂度:O(N^3)
动态规划解法：

状态初始化为False

dp[i][j]回文：s[i]=s[j]且[i-1:j-1]也为回文

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # if s==s[::-1]:
        #     return s
        # #超限
        # t=''
        # n=''
        # for i in range(len(s)):
        #    for j in range(i+1,len(s)+1):
        #         t=s[i:j]
        #         if t==t[::-1] and len(n)<len(t):
        #             n=t
        # return n
        '''
        动态规划来解：dp[i][j]与dp[i+1][j-1]有关    [i:j]为回文，则s[i]=s[j]且[i-1:j-1]也为回文
        j-i<=1情况:   aba    ab    代表字符串长度为奇、偶情况
        '''
        n=''
        dp=[[False]*len(s) for _ in range(len(s))]
        for i in range(len(s)-1,-1,-1):
            for j in range(len(s)-1,i-1,-1):
                if s[i]==s[j]:
                    if j-i<=1:
                        dp[i][j]=True
                    elif dp[i+1][j-1]:
                        dp[i][j]=True
                if dp[i][j] and (j+1-i)>len(n):
                    n=s[i:j+1]
        return n