Python实现常见回文字符串算法详解
本文详解Python中常见的回文字符串处理算法，涵盖暴力破解、动态规划及Manacher算法。重点解析最长回文子串、前缀及子序列的求解思路，提供完整代码实现与复杂度分析，帮助开发者高效解决回文相关问题。
回文
利用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
求解最长回文子串
暴力破解法
暴力破解法通过枚举所有可能的子串，并逐一判断其是否为回文。该方法的时间复杂度为O(n^3)。
动态规划法
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)。
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数组，具体推导过程可参考相关技术文章。
以下是Manacher算法的具体Python实现代码。
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]为真时，状态转移方程为dp[i][j] = dp[i+1][j - 1] + 2。
- 当s[i] == s[j]为假时，状态转移方程为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)。
总结
以上介绍了Python实现常见回文字符串算法的方法，希望能为读者提供帮助。如有任何疑问，欢迎留言交流，我们将及时回复。感谢大家对本站的支持！
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
