[Leetcode][python]Longest Palindromic Substring/最长回文子串
[Leetcode][python]Longest Palindromic Substring/最长回文子串
蛮三刀酱
发布于 2019-03-26 17:06:06
发布于 2019-03-26 17:06:06
题目大意
给出一个字符串S，找到一个最长的连续回文串。
解题思路
经典讲解参考： https://www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Par-I.html#_labelTop
暴力穷举法O(N3) 显然有C(N,2)（组合）个子串。检测每个子串都需要O(N)的时间，所以此方法的时间复杂度为O(N3)。
动态规划O(N2)时间O(N2)空间 定义二维数组P[i,j]用以表示Si…Sj是回文（true）或不是回文（false）
那么可知状态转移方程：P[i,j] = (P[i + 1, j - 1] && Si ==Sj)
初始条件是：P[i, i] = true，P[i, i + 1] = (Si == Si+1)
这个DP法的思路就是，首先可以知道单个字符和两个相邻字符是否回文，然后检测连续三个字符是否回文，然后四个。
此算法时间复杂度O(N2)，空间复杂度O(N2)。
注意： 1.判断空字符串 2.这题遍历切不可横向遍历，否则例如abcba，是无法先将bcb置为1的，进而无法将abcba置为1。 应该如图所示，向右下方先遍历。(后来想想，从下面开始横向遍历也是可以的，只是不可从上面)
这里写图片描述
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return ''
# 先将任一单个字母作为结果
start = 0
maxlen = 1
dp = [[0 for __ in range(len(s))] for __ in range(len(s))]
# 将长度1和长度2（相同字母）情况初始化赋值
for i in range(len(s)):
dp[i][i] = 1
if (i < len(s) - 1) and (s[i] == s[i+1]):
dp[i][i+1] = 1
start = i
maxlen = 2
# for line in dp:
# print line
# 注意：不可横向遍历，否则例如abcba，是无法先将bcb置为1的，进而无法将abcba置为1
# 从长度3开始
for length in range(3, len(s)+1):
for i in range(len(s)-length+1):
j = i + length - 1
if (dp[i+1][j-1] == 1) and s[i] == s[j]:
dp[i][j] = 1
if length > maxlen:
start = i
maxlen = length
# for line in dp:
# print line
return s[start:start+maxlen]中心检测法
下面介绍一个O(N2)时间O(1)空间的算法。
回文的特点，就是中心对称。对于有N个字符的字符串S，只有2N-1个中心。
为何是2N-1？因为两个字符之间的空档也可以是一个中心。例如”abba”的两个b中间就是一个中心。
围绕一个中心检测回文需要O(N)时间，所以总的时间复杂度是O(N2)。
class Solution(object):
def getlongestpalindrome(self, s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1 : r] # 例如bab，最后l=-1，r=3，所以要s[l+1 : r]也就是[0,3]
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
palindrome = ''
for i in range(len(s)):
len1 = len(self.getlongestpalindrome(s, i, i)) # len1是中间是单一字母的回文数
if len1 > len(palindrome):
palindrome = self.getlongestpalindrome(s, i, i)
len2 = len(self.getlongestpalindrome(s, i, i + 1)) # len2是中间是和后面一个字母相同的回文数
if len2 > len(palindrome):
palindrome = self.getlongestpalindrome(s, i, i + 1)
return palindrome总结
- 回文有两种可能：aba和abba
- 此题动态规划通过效率不高，不如中心检测法
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年08月08日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录