Daily LeetCode 5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

Medium

问题描述：

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

Example 1:

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

Example 2:

Input: "cbbd"
Output: "bb"

思路及代码：

这一题要求最长回文子串。

中间->两边：

回文串从中间向两边是镜像的状态，例如abba，中心为bb，或是aba，中心为a。因此，无论长度是奇数还是偶数，回文串都关于中间一个或是两个字符对称。因此，我们只需要遍历一边输入串s，分别考虑以s[i]或s[i]&s[i+1]为中心的最长回文串即可。

我们设置一个辅助函数，接受参数为：

• s：输入串
• start：回文串起点
• end：回文串终点

返回当前情况下最长的回文子串。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(s, start, end):
            while start >= 0 and end <= len(s) - 1 and s[start] == s[end]:
                start -= 1
                end += 1

            return s[start + 1:end]

        if len(s) <= 1 or not s:
            return s

        res = s[0:1]
        for i in range(len(s)):
            tmp = expand(s, i, i)
            if len(tmp) > len(res):
                res = tmp
            tmp = expand(s, i, i + 1)
            if len(tmp) > len(res):
                res = tmp

        return res        

动态规划：

对于这种求子串的问题，我们可以用动态规划的思想来解决，维护一个二维数组dp，dp[i][j]表示以i为起点、j为终点的子串是否为回文串。我们需要考虑三种情况：

• i=j时，dp[i][j]始终等于1
• j=i+1时，此时就是往长度为1的串中添加一个字符，只需要考虑s[i]是不是等于
  s[j]，若相等，则为回文串
• j>i+1时，此时等价于向以i-1为起点、j+1为终点的字符串两边加字母，我们需要考虑两个条件，一是字符串s[i-1:j+1]是不是回文串，二是待添加的字符s[i]与s[j]是否相等，均满足时，才可以得到一个新的回文串。

在遍历过程中，我们还需要更新变量start和length，当前回文串的长度为i-j+1，在遍历过程中，确保回文串长度最大，同时更行回文串起点，这样能够方便获取结果。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return s
        dp = [[0] * len(s) for _ in range(len(s))]
        start, length = 0, 1
        for i in range(len(s)):
            dp[i][i] = 1
            for j in range(i):
                if s[i] == s[j] and (i - j < 2 or dp[j + 1][i - 1]):
                    dp[j][i] = 1
                if dp[j][i] and length < i - j + 1:
                    length = i - j + 1
                    start = j

        return s[start:start + length]