5. Longest Palindromic Substring

先来一个动态规划版

• dp是n*n的，dp[i][j]代表i到j是不是回文
• j从0到n，i从0到j，为什么不从j到n，因为dp[i][j]会用到dp[i+1][j-1]，j+1还没遍历到
• 注意先更新dp[j][j]=True，否则会出错
• 状态转移公式：s[i] == s[j] and (j-i<=1 or dp[i+1][j-1])

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) <= 1:
            return s
        dp = [[False for i in range(len(s))] for j in range(len(s))]
        maxlen = start = end = 0
        for j in range(len(s)):
            dp[j][j] = True
            for i in range(j):
                if s[i] == s[j] and (j-i<=1 or dp[i+1][j-1]):
                    dp[i][j] = True
                    if j - i + 1 > maxlen:
                        start = i
                        end = j 
                        maxlen = j - i + 1
        return s[start:end+1]

从中间往两边扩散

• 由于奇数和偶数不一样，所以要分开。
• 注意更新left 和right

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) <= 1:
            return s
        maxlen = l = r = 0
        for i in range(len(s)):
            for j in range(2):
                left = i
                right = left + j
                while left >= 0 and right < len(s) and s[left] == s[right]:
                    left -= 1
                    right += 1
                left += 1
                right -= 1
                if right - left + 1 > maxlen:
                    l = left
                    r = right
                    maxlen = right - left + 1
        return s[l:r+1]