利用python解决最长回文子串力扣

### 暴力解法 暴力解法是最容易想到的方法，其核心思想是截取字符串的所有子串，然后逐一判断这些子串是否为回文，并记录最长的回文子串。这种方法虽然直观，但效率较低，时间复杂度为 $O(n^3)$，因为需要遍历所有可能的子串（$O(n^2)$），并对每个子串进行回文检查（$O(n)$）。 以下是使用暴力解法的Python实现： ```python class Solution: def longestPalindrome(self, s: str) -> str: if len(s) < 2: return s start = 0 # 记录最长回文子串开始的位置 max_len = 0 # 记录最长回文子串的长度 for i in range(len(s) - 1): for j in range(i, len(s)): if j - i < max_len: continue if self.is_palindrome(s, i, j): max_len = j - i + 1 start = i return s[start:start + max_len] def is_palindrome(self, s: str, left: int, right: int) -> bool: while left < right: if s[left] != s[right]: return False left += 1 right -= 1 return True ``` ### 动态规划方法 动态规划是一种更高效的解决方案，它通过存储中间结果来避免重复计算。定义一个二维数组 `dp` 来表示子串是否为回文。如果 `s[i:j+1]` 是回文，则 `dp[i][j] = True`；否则为 `False`。状态转移方程如下： - 如果 `s[i] == s[j]` 且 `i+1 > j-1`（即子串长度小于等于3），则 `dp[i][j] = True`。 - 如果 `s[i] == s[j]` 且 `dp[i+1][j-1]` 为 `True`，则 `dp[i][j] = True`。 下面是基于动态规划的Python实现： ```python class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] max_len = 1 start = 0 for j in range(n): for i in range(j + 1): if i == j: dp[i][j] = True elif s[i] == s[j]: if j - i <= 2: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] if dp[i][j] and j - i + 1 > max_len: max_len = j - i + 1 start = i return s[start:start + max_len] ``` ### 中心扩展法 中心扩展法利用了回文串的对称性，通过枚举每一个可能的中心点并尝试向两边扩展，找到最长的回文子串。由于回文可以是奇数长度或偶数长度，因此需要考虑两种情况：以单个字符为中心（奇数长度）和以两个字符为中心（偶数长度）。 以下是使用中心扩展法的Python实现： ```python class Solution: def longestPalindrome(self, s: str) -> str: if len(s) < 2: return s start = 0 max_len = 0 def expand(left: int, right: int) -> tuple: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return (left + 1, right - 1) for i in range(len(s)): l1, r1 = expand(i, i) l2, r2 = expand(i, i + 1) if r1 - l1 > max_len: start, max_len = l1, r1 - l1 if r2 - l2 > max_len: start, max_len = l2, r2 - l2 return s[start:start + max_len + 1] ``` ### 总结 - **暴力解法** 简单直接，但效率较低，适合理解问题的基本思路。 - **动态规划** 通过存储中间结果优化了性能，适用于较长的字符串。 - **中心扩展法** 利用了回文串的特性，仅需线性空间，时间和空间效率都较好。 每种方法都有其优缺点，在实际应用中可以根据具体需求选择合适的算法。对于LeetCode上的测试用例，这三种方法都可以正确解决问题，但在处理大数据集时，动态规划和中心扩展法更为高效[^1]。