求最长回文子串python代码
时间: 2024-05-02 08:14:14 浏览: 71
求最长回文子串是一个经典的问题,可以使用动态规划或者中心扩展法来解决。下面是使用动态规划的Python代码示例:
```python
def longestPalindrome(s):
n = len(s)
# 创建一个二维数组dp,dp[i][j]表示s[i:j+1]是否为回文子串
dp = [[False] * n for _ in range(n)]
start = 0 # 记录最长回文子串的起始位置
max_len = 1 # 记录最长回文子串的长度
# 初始化长度为1和2的回文子串
for i in range(n):
dp[i][i] = True
if i < n - 1 and s[i] == s[i + 1]:
dp[i][i + 1] = True
start = i
max_len = 2
# 动态规划,从长度为3开始逐渐增加
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
start = i
max_len = length
return s[start:start + max_len]
# 测试代码
s = "babad"
result = longestPalindrome(s)
print(result)
```
阅读全文