常见的回文字符串算法题目

回文

所谓回文就是字符串的顺读与逆读都相同, 关于回文字符串有下列几种常见的算法题

串:连续的串
序列: 顺序保持的序列(不需要是连续的)

判断回文

利用python 自带的翻转 函数reversed()

def is_plalindrome(string):
return string == ''.join(list(reversed(string)))

当然也可以自己实现

def is_plalindrome(string):
string = list(string)
length = len(string)
left = 0
right = length - 1
while left < right:
if string[left] != string[right]:
return False
left += 1
right -= 1
return True

利用python 提供的标准库 profile 来对上面的两种方案进行测试,第一种实现会相对更快,大约是第二种实现的1.2倍

最长的回文子串

暴力破解

暴力破解,枚举所有的子串,对每个子串判断是否为回文, 时间复杂度为 O(n^3)

动态规划法

  • dp[i][j] 表示子串 s[i..j] 是否回文
  • 初始化 dp[i][i] = true (0 <= i <= n - 1), 其余初始化为 false
  • dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1] == true)
def solution(s):
s = list(s)
l = len(s)
dp = [[0] * l for i in range(l)]
for i in range(l):
dp[i][i] = True
# 当 k = 2时要用到
dp[i][i - 1] = True
resLeft = 0
resRight = 0
# 枚举子串的长度
for k in range(2, l+1):
# 子串的起始位置
for i in range(0, l-k+1):
j = i + k - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
# 保存最长的回文起点和终点
if resRight - resLeft + 1 < k:
resLeft = i
resRight = j
return ''.join(s[resLeft:resRight+1])

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

定位元素拓展长度

以某个元素为中心,分别计算偶数长度的回文最大长度和奇数长度的回文最大长度

例如:
a b b c b b
当 i = 2时,即 s[i] => b, 以 i-1,i 元素为中心计算偶数长度的回文最大长度为2, 为 bb;以 i 为中心计算奇数长度的回文最大长度为1, 为 b

当 i = 4 时,以 i-1,i 元素为中心计算偶数长度的回文最大长度为1, 为 b;以 i 为中心计算奇数长度的回文最大长度为5, 为 bbcbb

在这个过程维持一个回文最大长度和起始位置

def solution2(s):
length = len(s)
if not length:
return 0
start = maxLen = 0
for i in range(1, length):
low = i - 1
high = i
while low >= 0 and high < length and s[low] == s[high]:
low -= 1
high += 1
if high - low - 1 > maxLen:
maxLen = high - low - 1
start = low + 1
low = i - 1
high = i + 1
while low >= 0 and high < length and s[low] == s[high]:
low -= 1
high += 1
if high - low - 1 > maxLen:
maxLen = high - low - 1
start = low + 1
return s[start:start+maxLen]

该算法的时间复杂度为 O(n^2), 空间复杂度为O(1)

Manacher 算法

上面的定位元素拓展算法存在一些缺陷

  • 回文子串的奇偶性造成不同性质的对称轴位置,导致算法要分两种情况
  • 很多子串被重复访问

为了解决上述问题, Manacher 算法就是针对这些问题的改进算法

Manacher 算法首先对字符串做一个预处理,使得所有的串都是奇数长度, 插入的是同样的符号且符号不存在与原串中,串的回文性不受影响

aba => #a#b#a#
abab => #a#b#a#b#

我们把回文串中最右位置与其对称轴的距离称为回文半径,Manacher 算法定义了一个回文半径数组 RL,RL[i]表示以第 i 个字符为对称轴的回文半径,对于上面得到的插入分隔符的串来说,我们可以得到 RL数组

char: # a # b # a #
RL: 1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0
i: 0 1 2 3 4 5 6
char: # a # b # a # b #
RL: 1 2 1 4 1 4 1 2 1
RL-1: 0 1 0 3 0 3 0 1 0
i: 0 1 2 3 4 5 6 7 8

我们还求了 RL[i] - 1: 我们发现RL[i] -1 正好是初始字符串中以位置i 为对称轴的最长回文长度

所以下面就是重点如何求得 RL 数组了, 可以参考这篇文章 (讲得比较清晰)

下面是算法实现

def manacher(preS):
s = '#' + '#'.join(preS) + '#'
l = len(s)
RL = [0] * l
maxRight = pos = maxLen = 0
for i in range(l):
if i < maxRight:
RL[i] = min(RL[2*pos - i], maxRight-i)
else:
RL[i] = 1
while i - RL[i] >= 0 and i + RL[i] < l and s[i - RL[i]] == s[i + RL[i]]:
RL[i] += 1
if i + RL[i] - 1 > maxRight:
maxRight = i + RL[i] - 1
pos = i
maxLen = max(RL)
idx = RL.index(maxLen)
sub = s[idx - maxLen + 1: idx + maxLen]
return sub.replace('#', '')

空间复杂度:借助了一个辅助数组,空间复杂度为 O(n)
时间复杂度:尽管内层存在循环,但是内层循环只对尚未匹配的部分进行,对于每一个字符来说,只会进行一次,所以时间复杂度是 O(n)

最长回文前缀

所谓前缀,就是以第一个字符开始

下面的最长回文前缀

abbabbc => abbc
abababb => ababa
sogou => s

将原串逆转,那么问题就转变为求原串的前缀和逆串后缀相等且长度最大的值, 这个问题其实就是 KMP 算法中的 next 数组的求解了

具体求解: 将原串逆转并拼接到原串中, 以’#’ 分隔原串和逆转避免内部字符串干扰。

def longest_palindrome_prefix(s):
if not s:
return 0
s = s + '#' + s[::-1] + '$'
i = 0
j = -1
nt = [0] * len(s)
nt[0] = -1
while i < len(s) - 1:
if j == -1 or s[i] == s[j]:
i += 1
j += 1
nt[i] = j
else:
j = nt[j]
return nt[len(s) - 1]

添加字符生成最短回文字符串

这道题其实跟上面基本是一样的,
实例:

aacecaaa -> aaacecaaa # 添加 a
abcd -> dcbabcd # 添加 dcb

我们先求字符串的最长回文前缀, 然后剩余的字符串逆转并拼接到字符串的头部即是问题所求

def solution(s):
length = longest_palindrome_prefix(s)
return s[length:][::-1] + s

最长回文子序列

动态规划法

  • dp[i][j] 表示子序列 s[i..j] 中存在的最长回文子序列长度
  • 初始化dp[i][i] = 1
  • 当 s[i] == s[j] 为 true 时,dp[i][j] = dp[i+1][j - 1] + 2
  • 当 s[i] == s[j] 为 false 时,dp[i][j] = max(dp[i+1][j], dp[i][j - 1])
# 求得最长回文子序列的长度
def solution(s):
l = len(s)
dp = [[0] * l for i in range(l)]
for i in range(l):
dp[i][i] = 1
# 枚举子串的长度
for k in range(2, l+1):
# 枚举子串的起始位置
for i in range(0, l-k+1):
j = i + k - 1
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
return dp[0][l-1]

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

坚持原创技术分享