查找Python中最长回文子串长度的程序

Z时代
2024-01-10
分类：综合

假设我们有一个字符串S。我们必须找到S中最长回文子字符串的长度。我们假设字符串S的长度为1000。因此，如果字符串为“ BABAC”，则最长回文子字符串为“ BAB” ”，长度为3。

为了解决这个问题，我们将遵循以下步骤-

定义一个与字符串长度相同阶数的方阵，并用False填充
将主要对角线元素设置为true，因此对于所有i从0到阶– 1的DP [i，i] = True
开始：= 0
对于范围2到长度S +1的l

结束：= i + l
如果l = 2，则
除此以外
DP [i，结束-1] = True，max_len：= l，开始：= i
如果S [i] = S [end-1]，则

DP [i，结束-1] = True，max_len：= l，开始：= i
如果S [i] = S [end-1]和DP [i + 1，end-2]，则

对于i，范围为0到S – l + 1的长度

返回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'))