转自Kindem的博客

问题

Given a string s,find the longest palindromic substring in s, You may assume that the maximum length of s is 1000

Example:

Input: "babab"
Output: "bab"
Note: "aba" is also a valid answer

Example:

Input: "cbbd"
Output: "bb"

说白了就是给你一个字符串，然后让你找出其中最长的回文子字符串

几种常见的解题思路

1. 大家最容易想到的，就是直接暴力撸，写一个函数验证一个字符串是不是回文字符串，然后把给出字符串中的所有子字符串验证，得出最长的回文字符串，不过显然，根据LeetCode的尿性，这种办法肯定是超过时限的
2. 滑动窗口验证，使用p和q标记窗口的开始和结束，然后使用验证函数验证窗口内的字符串是不是回文字符串，这种方法应该会好很多，能够通过LeetCode的时间限制，但是感觉从莫种意义上来说，还是不够快

一种巧妙解法

这种解法是动态规划加上规律分析：

1. 很明显，回文的验证可以使用递归函数，s[p+1:q+1]是一个回文字符串，当且仅当s[p:q]是一个回文字符串时成立，然后你懂得
2. 只要遍历字符串中的每一个字符，将这些字符作为验证的“核”，看是否成立，如果成立，记录长度并且与最大长度比较，然后你懂的

上Python3代码:

class Solution:
    def __checkIfNextPalindrome(self, s, p, q, count):
        if p - 1 < 0 or q + 1 > len(s) - 1:
            return [p, q, count]
        else:
            if s[p - 1] == s[q + 1]:
                return self.__checkIfNextPalindrome(s, p - 1, q + 1, count + 2)
            else:
                return [p, q, count]

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        ans = ''
        max = 0
        p = 0
        while p < len(s):
            q = p
            while q < len(s) and s[p] == s[q]:
                q += 1
            q -= 1
            tmp = self.__checkIfNextPalindrome(s, p, q, q + 1 - p)
            if tmp[2] > max:
                max = tmp[2]
                ans = s[tmp[0]:tmp[1] + 1]
            p += 1
        return ans