5. 最长回文子串

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        dp = [[False]*len(s) for _ in range(len(s))]
        
        # 结果跟踪器
        max_idx = -1
        max_len = 0
        
        # 每个元素本身都是一个回文串
        # 长度是 1
        # 解决了奇数的问题
        for i in range(len(s)):
            dp[i][i] = True
            max_idx = i
            max_len = 1
            
        # 对于两个相连的字符串进行判断
        # 长度是2
        # 解决了偶数的问题
        
        for i in range(1, len(s)):
            if s[i-1] == s[i]:
                dp[i-1][i] = True
                max_idx = i-1
                max_len =2
                
        # 从长度为3 to len(s)一次进行递推
        for strlen in range(3,len(s)+1):
            for i in range(0,len(s)-strlen+1):
                j = i+strlen -1
                
                # 更新条件
                if s[i] ==s[j] and dp[i+1][j-1] == True:
                    dp[i][j] = True
                    
                    # 更新一下跟踪器
                    if(strlen>max_len):
                        print max_idx, max_len
                        max_idx = i
                        max_len = strlen
        
        return s[max_idx:max_idx+max_len]