leetcode-005-Longest-Palindromic-Substring

发表于 | 更新于: | 分类于 |

leetcode-005-Longest-Palindromic-Substring 最长回文字串

1. 题目

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

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：

输入: “cbbd”
输出: “bb”

2. 解

动态规划：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        str_length = len(s)
        max_length = 0
        start = 0
        for i in range(str_length):
            if i - max_length >= 1 and s[i-max_length-1: i+1] == s[i-max_length-1: i+1][::-1]:
                start = i - max_length - 1
                max_length += 2
                continue
            if i - max_length >= 0 and s[i-max_length: i+1] == s[i-max_length: i+1][::-1]:
                start = i - max_length
                max_length += 1
        return s[start: start + max_length]