字符串处理题目背景
回文串是指一个字符串从左到右和从右到左读都是一样的。寻找一个字符串中的最长回文子串是许多经典算法问题之一，广泛应用于文本处理、数据分析和计算生物学等领域。
本题的挑战在于如何高效地找出最长的回文子串。在暴力搜索可能导致时间复杂度过高的情况下，掌握优化算法不仅可以提升代码性能，还能加深我们对字符串处理的理解。
题目描述
给定一个字符串 s，请你找出其中最长的回文子串。你可以假设 s 的最大长度为 1000。
输入描述
- 一个字符串
s，长度在[1, 1000]之间，且字符为小写字母。
输出描述
- 一个字符串，表示输入字符串中最长的回文子串。
示例
示例 ①
输入：
代码语言：javascript复制# 调用 longestPalindrome() 函数
print(longestPalindrome("babad"))输出：
代码语言：javascript复制"bab"解释：回文子串有 “bab” 和 “aba”，长度均为 3，返回其中一个即可。
示例 ②
输入：
代码语言：javascript复制print(longestPalindrome("cbbd"))输出：
代码语言：javascript复制"bb"解释：最长回文子串是 “bb”。
代码讲解与多种解法
解法一：暴力搜索法
最直接的解法是使用暴力搜索法，检查每一个子串是否为回文，并在检查时记录最长的回文子串。虽然该方法简单易懂，但它的时间复杂度为 O(n^3)，对于较长的字符串来说效率较低。
代码语言：javascript复制def longestPalindrome(s):
def is_palindrome(substring):
return substring == substring[::-1]
n = len(s)
max_len = 0
start = 0
for i in range(n):
for j in range(i, n):
if is_palindrome(s[i:j 1]) and (j - i 1) > max_len:
max_len = j - i 1
start = i
return s[start:start max_len]优点：
- 实现简单直观，易于理解。
缺点：
- 时间复杂度为 O(n^3)，对于长字符串性能较差。
解法二：中心扩展法
中心扩展法通过从字符串的每个位置向外扩展，寻找回文子串。这种方法利用回文串的对称性，能在 O(n^2) 的时间复杂度内找到最长的回文子串，较暴力搜索法有明显的性能提升。
代码语言：javascript复制def longestPalindrome(s):
if not s or len(s) == 1:
return s
def expand_around_center(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right = 1
return s[left 1:right]
max_palindrome = ""
for i in range(len(s)):
odd_palindrome = expand_around_center(i, i)
even_palindrome = expand_around_center(i, i 1)
max_palindrome = max(odd_palindrome, even_palindrome, max_palindrome, key=len)
return max_palindrome优点：
- 时间复杂度为 O(n^2)，较为高效。
- 代码较简洁，且适用于大多数实际场景。
缺点：
- 对于极端大数据量，仍然可能存在性能瓶颈。
解法三：动态规划法
动态规划法通过构建一个二维表来记录子串是否为回文，以此减少重复计算的次数。其时间复杂度同样为 O(n^2)，但在空间复杂度上会有额外的消耗 O(n^2)，适用于需要明确记录所有回文状态的情况。
代码语言：javascript复制def longestPalindrome(s):
n = len(s)
if n == 0:
return ""
dp = [[False] * n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True
for end in range(1, n):
for start in range(end):
if s[start] == s[end]:
if end - start == 1 or dp[start 1][end - 1]:
dp[start][end] = True
if end - start 1 > max_len:
max_len = end - start 1
longest_palindrome_start = start
return s[longest_palindrome_start:longest_palindrome_start max_len]优点：
- 可以记录所有子串的回文状态，便于追溯具体情况。
- 理论上稳定的 O(n^2) 时间复杂度，适合分析数据时使用。
缺点：
- 额外的 O(n^2) 空间复杂度，可能会导致空间使用过大。
解法四：马拉车算法
马拉车算法（Manacher’s Algorithm）是一种线性时间复杂度 O(n) 的算法。它利用回文的对称性，特别适合用于寻找最长回文子串。这是解决该问题的最优解，但其实现较为复杂。
代码语言：javascript复制def longestPalindrome(s):
t = '#' '#'.join(s) '#'
n = len(t)
p = [0] * n
c = r = 0
max_center = 0
for i in range(n):
mirror = 2 * c - i
if i < r:
p[i] = min(r - i, p[mirror])
while i p[i] 1 < n and i - p[i] - 1 >= 0 and t[i p[i] 1] == t[i - p[i] - 1]:
p[i] = 1
if i p[i] > r:
c, r = i, i p[i]
if p[i] > p[max_center]:
max_center = i
start = (max_center - p[max_center]) // 2
return s[start:start p[max_center]]优点：
- 时间复杂度为 O(n)，是最优解，适用于需要极高效率的场景。
- 对称性处理巧妙，可提升处理大数据集时的性能。
缺点：
- 实现复杂度较高，理解和编码难度大。
总结与思考
寻找最长回文子串的方法多样，从暴力搜索到马拉车算法，每种方法都有其优缺点：
- 暴力搜索法：尽管简单直观，但效率较低，仅适合处理小规模数据。
- 中心扩展法：通过中心向外扩展，以较高效率找到回文子串，适用于大部分实际应用。
- 动态规划法：利用子问题记录状态，能有效避免重复计算，但空间复杂度较高。
- 马拉车算法：在时间复杂度上最优，适用于处理大规模数据的高效需求。
在实际应用中，选择合适的算法不仅依赖于问题的规模和复杂度，还需考虑实现的难易程度和应用场景。
扩展思考
- 文本处理中的应用：回文子串在自然语言处理、数据压缩等领域有广泛应用，理解回文结构有助于我们更好地处理文本数据。
- 字符串匹配算法：通过学习最长回文子串的求解方法，我们还能拓展到字符串匹配等更复杂的问题。
- 时间复杂度优化：马拉车算法为 O(n) 的复杂度，为我们提供了极致优化的思路，值得在其他复杂算法问题中学习和借鉴。
通过本文的讲解，相信你已经对寻找最长回文子串的各种算法有了深入的理解，并掌握了处理类似字符串问题的技巧。
关注博客，解锁更多字符串处理技巧！ |
|---|
作者信息 作者 ： 繁依Fanyi CSDN： https://techfanyi.blog.csdn.net 掘金：https://juejin.cn/user/4154386571867191 |
|---|
