用 Python 编写程序来查找最长回文子串的长度
pythonserver side programmingprogramming更新于 2026/1/23 23:40:17
假设我们有一个字符串 S。我们必须找出 S 中最长回文子串的长度。我们假设字符串 S 的长度为 1000。因此，如果字符串是"BABAC"，则最长回文子串是"BAB"，长度为 3。
为了解决这个问题，我们将遵循以下步骤 −
定义一个与字符串长度相同阶的方阵，并用 False 填充它
将主对角线元素设置为 true，因此对于从 0 到阶的所有 i，DP[i, i] = True – 1
start := 0
对于 l，范围为 2 到 S 的长度 + 1
对于 i，范围为 0 到 S 的长度 – l + 1
end := i + l
如果 l = 2，则
如果 S[i] = S[end - 1]，则
DP[i, end - 1] = True，max_len := l，且 start := i
否则
如果 S[i] = S[end - 1] 且 DP[i + 1, end - 2]，则
DP[i, end - 1] = True，max_len := l，且 start := i
返回 max_len
让我们看看下面的实现以便更好地理解 −
示例
class Solution(object):
def solve(self, s):
dp = [[False for i in range(len(s))] for i in range(len(s))]
for i in range(len(s)):
dp[i][i] = True
max_length = 1
start = 0
for l in range(2,len(s)+1):
for i in range(len(s)-l+1):
end = i+l
if l==2:
if s[i] == s[end-1]:
dp[i][end-1]=True
max_length = l
start = i
else:
if s[i] == s[end-1] and dp[i+1][end-2]:
dp[i][end-1]=True
max_length = l
start = i
return max_length
ob = Solution()
print(ob.solve('BABAC'))
输入
"ABBABBC"
输出
5
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
