【LeetCode 5 动态规划】最长回文子串

文章目录

• • 1. 题目
  • • 1.1 示例
    • 1.2 说明
    • 1.3 限制
  • 2. 解法一（暴力求解法）
  • • 2.1 分析
    • 2.2 解答
    • 2.3 复杂度
  • 3. 解法二（中心扩展法）
  • • 3.1 分析
    • 3.2 解答
    • 3.3 复杂度
  • 4. 解法三（动态规划法）
  • • 4.1 分析
    • • 4.1.1 定义状态
      • 4.1.2 状态转移
      • 4.1.3 边界条件
      • 4.1.4 状态初始化
    • 4.2 解答
    • 4.3 复杂度

1. 题目

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

1.1 示例

• 示例 $1$ ：

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

• 示例 $2$ ：

  • 输入： s = "cbbd" ；
  • 输出： "bb" 。

1.2 说明

• 来源： 力扣（LeetCode）
• 链接： https://leetcode-cn.com/problems/longest-palindromic-substring/

1.3 限制

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

2. 解法一（暴力求解法）

2.1 分析

本题使用暴力求解的方法很简单，即枚举出 s 的所有可能子串，找到其中一个最长的回文串即可。

针对下面实现，需要注意的是，使用了一个单独封装的方法 _is_palindrome() 来判断从给定字符串 s 的索引 left 到 right 之间确定的子串是否为回文串。

2.2 解答

class Solution:
    def _is_palindrome(self, s: str, left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def longest_palindrome(self, s: str) -> str:
        s_length = len(s)
        p_length = 0
        p_start = p_stop = 0
        for i in range(s_length):
            for j in range(i, s_length):
                if self._is_palindrome(s, i, j) and j - i + 1 > p_length:
                    p_length = j - i + 1
                    p_start = i
                    p_stop = i + p_length
        return s[p_start:p_stop]


def main():
    sln