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


假设我们有一个字符串 S。我们需要找到 S 中最长回文子串的长度。我们假设字符串 S 的长度为 1000。所以如果字符串是“BABAC”,那么最长回文子串是“BAB”,长度为 3。

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

  • 定义一个与字符串长度相同的方阵,并将其全部填充为 False

  • 将主对角线元素设置为 True,因此对于所有从 0 到 order – 1 的 i,DP[i, i] = True

  • start := 0

  • for l in range 2 to length of S + 1

    • for i in range 0 to length of 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"

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

5

更新于: 2020年10月10日

557 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告