最长回文子串

5. 最长回文子串

题目描述

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

示例 1：

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

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

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

解题思路

• 方法1: 暴力法
  暴力法将选出所有子字符串可能的开始和结束位置，并检验它是不是回文。
• 方法2: 动态规划

代码实现

• 方法1:

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if s == s[::-1]:
            return s
        max_len = 1
        res = s[0]
        for i in range(len(s) - 1):
            for j in range(i+1, len(s)):
                if j - i + 2 > max_len and s[i:j+1] == s[i:j+1][::-1]:   # j - i + 几 无所谓, 只要大于max_len就行了
                    max_len = j - i + 2
                    res = s[i:j + 1]
        return res