[5][中等][动态规划] 最长回文子串

题目描述

5. 最长回文子串

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

示例 1：

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

示例 2：

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

解题思路

中心扩展

回文串一定是对称的, 所以我们可以每次选择一个中心, 进行左右扩展, 判断左右字符是否相等即可.

由于存在对称中心是奇数或偶数的情况, 所有共有$2N - 1$个中心, $N$是字符串的长度.

这种方法是比较直观的方法, 时间复杂度$O(N^2)$, 空间复杂度$O(1)$

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ''

        max_len = 1
        left = right = 0
        for i in range(n):
            len1 = self.center_search(i, i, s)
            len2 = self.center_search(i, i + 1, s)
            len3 = max(len1, len2)
            if len3 > max_len:
                left = i - (len3 - 1) // 2
                right = i + len3 // 2
                max_len = len3
        return s[left: right + 1]

    def center_search(self, i, j, s):
        while i >= 0 and j < len(s) and s[i] == s[j]:
            i -= 1
            j += 1
        return j - i - 1

动态规划

动态规划的解法参考:

• 详细通俗的思路分析，多解法

• 动态规划、中心扩散、Manacher 算法

第一篇对动态规划的状态, 状态转移方程, 边际条件描述的更清楚, 并且考虑了空间优化的问题, 降低了空间复杂度.

第二篇详细讲解了, 根据状态转移方程的特点, 迭代的方向的选择及其原因, 也为第一篇文中的空间优化的循环方式, 做了更为清晰的解释.

此题采用动态规划的思路, 空间复杂度为$O(n^2)$, 下面的代码为空间优化的版本, 对应的空间复杂度为$O(n)$.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ''

        p = [False] * n
        cur_start, cur_length = 0, 1
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, i - 1, -1):
                t = False
                if j - i > 1 and p[j - 1] and s[i] == s[j]:
                    t = True
                elif j - i == 1 and s[i] == s[j]:
                    t = True
                elif j == i:
                    t = True
                elif j < i:
                    break

                p[j] = t
                if t and (j - i + 1) > cur_length:
                    cur_start = i
                    cur_length = j - i + 1
        return s[cur_start: cur_start + cur_length]

Manacher Algorithm

Manacher算法参考详细通俗的思路分析，多解法.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ''

        string = '#' + '#'.join(list(s)) + '#'
        n = len(string)
        p = []
        center, right = -1, -1
        for i in range(n):
            cur = 0
            mirror = 2 * center - i
            if i < right and mirror >= 0:  # 当前位置已经超出了最右的位置, 需要重新以当前位置为中心, 向外搜索
                cur = min(right - i, p[mirror])

            while i - cur - 1 >= 0 and i + cur + 1 < n and string[i - cur - 1] == string[i + cur + 1]:
                cur += 1

            if i + cur > right:
                right = i + cur
                center = i
            p.append(cur)

        center, rad = max([(i, t) for i, t in enumerate(p)], key=lambda x: x[1])
        return string[center - rad: center + rad].replace('#', '')