问题描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

使用动态规划解题。关于动态规划，请参考：https://github.com/tim-chow/DataStructure/tree/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92。

设置二维数组 dp，若子串 s[i ... j] 是回文字符串，则 dp[i][j] = True，否则 dp[i][j] = False。状态转移方程为：

• 如果 i == j，则 dp[i][j] = True
• 如果 s[i] != s[j]，则 dp[i][j] = False；否则：
  • 如果 j - i < 3，则 dp[i][j] = True
  • 否则 dp[i][j] = dp[i + 1][j - 1]

本题中的状态转移方程是从中间向两边递推的，因此需要注意循环顺序：

for j from 1 to len(s) - 1 {
    for i from 0 to j {
        DO SOMETHING;
    }
}

Python 实现

class Solution:
    def longestPalindrome(self, s):
        size = len(s)
        if size < 2:
            return s

        dp = [[False for _ in range(size)] for _ in range(size)]
        max_len = 1
        start = 0

        for j in range(1, size):
            for i in range(0, j + 1):
                if i == j:
                    dp[i][j] = True
                elif s[i] == s[j]:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                else:
                    dp[i][j] = False

                if dp[i][j]:
                    cur_len = j - i + 1
                    if cur_len > max_len:
                        max_len = cur_len
                        start = i
        return s[start:start + max_len]