LeetCode 5. 最长回文子串

题目

给你一个字符串 s，找到 s 中最长的回文子串。

例：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

方法：动态规划

思路同 647. 回文子串，区别在于本题不需要计算可以分割成的回文串的个数，而是记录可以分割成的最长的回文串

• dp[i][j] 表示下标为 [i, j] 组成的字符串是否为回文串，True 表示为回文串，False 表示不为回文串
• length 记录最长回文串的长度，left 和 right 分别记录最长回文串的起始和末尾下标
• result 记录最长回文串
• 外部循环为从下到上的循环，内部循环为从左到右的循环
  • 若首尾字符不同，那么一定不为回文串
  • 若首尾字符相同，那么需要继续判断：若 i=j，即此时只有一个字符（e.g. a），那么一定为回文串；若 j-i=1，即只有两个字符且相等（e.g. aa），那么一定为回文串；若 j-i>1，即首尾字符间存在其他字符，那么此时应判断下标为 [i+1, j-1] 组成的字符串是否为回文串，即 dp[i+1][j-1]
  • 若 [i, j] 组成的字符串为回文串，且该回文串的长度大于之前回文串的最大长度，那么更新回文串的最大长度，并记录该回文串的首尾在原字符串的下标
• 循环遍历回文串，记录该回文串于 result 列表
• 返回字符串形式的最长回文串

class Solution(object):
    def longestPalindrome(self, s):
        dp = [[False] * len(s) for row in range(len(s))]
        length = 0
        left, right = 0, 0
        result = []
        for i in range(len(s)-1, -1, -1):
            for j in range(i, len(s)):
                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 length < j-i+1:
                        length = j-i+1
                        left = i
                        right = j
        for i in range(left, right+1):
            result.append(s[i])
        return ''.join(result)