LeetCode习题解析-Longest Palindromic substring

问题

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