给你一个字符串 s,找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 Input 输入:长度不大于100的非空字符串s,区分大小写. Output 输出: 字符串s中包含的最长回文串的长度.
时间: 2025-06-25 12:23:48 浏览: 7
### 找到字符串中的最长回文子串及其长度
要解决这个问题,可以采用动态规划的方法来实现。通过构建一个二维布尔数组 `dp` 来记录子串是否为回文子串的状态。对于任意两个索引 `(i, j)`,如果满足条件 `s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1])`,则说明子串 `s[i:j+1]` 是回文子串[^1]。
以下是完整的解决方案:
#### 动态规划解法
定义状态转移方程如下:
- 如果 `s[i] != s[j]`,那么子串 `s[i:j+1]` 不可能是回文。
- 如果 `s[i] == s[j]` 并且子串长度小于等于 3 (`j - i <= 2`) 或者内部子串已经是回文 (`dp[i+1][j-1] == True`),那么当前子串也是回文。
最终目标是从所有可能的回文子串中找出最长的那个,并返回它的长度。
下面是基于上述逻辑的具体 Python 实现代码:
```python
def longest_palindrome(s: str) -> tuple:
n = len(s)
if n < 2:
return s, n
start = 0
max_len = 1
dp = [[False]*n for _ in range(n)]
# 单个字符都是回文
for i in range(n):
dp[i][i] = True
# 枚举子串长度
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
if j - i < 3 or dp[i+1][j-1]: # 判断是否为回文
dp[i][j] = True
if length > max_len:
start = i
max_len = length
return s[start:start+max_len], max_len
# 测试函数
result_str, result_length = longest_palindrome("babad")
print(f"最长回文子串为 {result_str},其长度为 {result_length}")
```
此代码的时间复杂度为 O(n²),空间复杂度也为 O(n²)[^2]。
#### 结果解释
运行以上程序后,将会得到输入字符串中的最长回文子串以及该子串的长度。例如,在测试用例 `"babad"` 中,输出的结果将是其中一个最长回文子串 `"bab"` 和对应的长度 `3`。
---
阅读全文
相关推荐












