[LeetCode]5 最长回文子串

题目描述

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

示例1:

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

示例2:

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
        if length<2 or (s==s[::-1]):
            return s
        max_len, start = 1, 0
        for i in range(1, length):
            typestr1 = s[i-max_len-1 : i+1]
            typestr2 = s[i-max_len : i+1]
            if (i-max_len >=1) & (typestr1 == typestr1[::-1]):
                start = i-max_len-1
                max_len += 2
                continue
            if (i-max_len >=0) & (typestr2 == typestr2[::-1]):
                start = i-max_len
                max_len += 1
        return s[start : start+max_len]