最长回文子串

一、题目

image-20231207224707335

二、解法

1、动态规划

根据回文串的定义，回文串的子串也必然是回文串： \[ P(i,j)=\begin{cases}\mathrm{truc},如果子串是回文串\\\mathrm{false},其他情况&\end{cases} \] 可以得到回文串的动态规划边界条件： \[ \begin{cases}P(i,i)=\text{true}\\P(i,i+1)=(S_i==S_{i+1})\end{cases} \] 最终答案即是所有\(P(i,j)=\text{true}\)中\(j-i+1\)(子串长度)的最大值。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        s_length  = len(s)

        if s_length <2:
            return s

        max_length = 1 
        begin = 0
        dp = [[False]*s_length for _ in range(s_length)]

        for i in range(s_length):
            dp[i][i] = True

        for L in range(2,s_length+1):

            for i in range(s_length):

                j = L + i - 1

                if j >=s_length:
                    break

                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    if j - i<3:
                        dp[i][j] =True
                    else:
                        dp[i][j] = dp[i+1][j-1]

                if dp[i][j] and j-i+1 > max_length:
                    max_length = j-i+1
                    begin = i

        return s[begin : begin + max_length]

复杂度

• 时间复杂度：\(O(n^2)\)
• 空间复杂度：\(O(n^2)\)

2、中心扩展法

该方法可以理解成第一种方法的逆向思维：即以最短的回文串不断左右扩展，找到最长的回文串。

class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

复杂度

• 时间复杂度：\(O(n^2)\)
• 空间复杂度：\(O(1)\)

3、Manacher（暂时没看懂）

image-20231207232341114

class Solution:
    def expand(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return (right - left - 2) // 2

    def longestPalindrome(self, s: str) -> str:
        end, start = -1, 0
        s = '#' + '#'.join(list(s)) + '#'
        arm_len = []
        right = -1
        j = -1
        for i in range(len(s)):
            if right >= i:
                i_sym = 2 * j - i
                min_arm_len = min(arm_len[i_sym], right - i)
                cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)
            else:
                cur_arm_len = self.expand(s, i, i)
            arm_len.append(cur_arm_len)
            if i + cur_arm_len > right:
                j = i
                right = i + cur_arm_len
            if 2 * cur_arm_len + 1 > end - start:
                start = i - cur_arm_len
                end = i + cur_arm_len
        return s[start+1:end+1:2]