LeetCode #4 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算法

 

 

（未完待续）

转载于:https://www.cnblogs.com/sbj123456789/p/11561310.html