LeetCode #5 Longest Palindromic Substring

Question

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"

方法一：暴力枚举

枚举所有的子串，共O(n^2)次，再对每一个子串检查是否是回文的，花费时间O(n)，所以一共O(n^3)

方法二：动态规划

先确定状态：状态f(i, j) 表示从i到j的子串是否是回文的，是值为1，不是值为0

容易写出状态转移方程：

　　当 s[i] == s[j] 时，f(i, j) = f(i+1, j-1) 

　　当 s[i] == s[j] 且 i+1 == j 时，f(i, j) = 1

　　当 i == j 时，f(i, j) = 1

class Solution:
    
    def longestPalindrome(self, s: str) -> str:
        len_s = len(s)
        longest_start = 0
        longest_end = 0
        longest_length = 1
        dp = [[0 for i in s] for j in s]
        for j in range(len_s):
            for i in range(j+1):
                if s[i] == s[j] and (j-i <= 1 or dp[i+1][j-1]) :
                    dp[i][j] = 1
                if dp[i][j] == 1 and j-i+1 > longest_length:
                    longest_start = i
                    longest_end = j
                    longest_length = j - i + 1
        return s[longest_start:longest_end+1]
    

时间复杂度为O(n^2)

此方法枚举时从左往右枚举；也可以从一个回文子串的中间向两边枚举，不用动归

方法三：Manacher算法

 

（未完待续）