[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 ''

        string = '#' + '#'.join(list(s)) + '#'
        n = len(string)
        p = []
        center, right = -1, -1
        mcenter, mrad = -1, -1
        for i in range(n):
            cur = 0
            mirror = 2 * center - right
            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

            if cur > mrad:
                mcenter = i
                mrad = cur
            p.append(cur)

        return string[mcenter - mrad: mcenter + mrad].replace('#', '')

动态规划

动态规划的解法参考:

• 详细通俗的思路分析，多解法
• 动态规划、中心扩散、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 - right
            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('#', '')