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


假设我们有一个小写字符串 s;我们需要找出 s 中最长回文子序列的长度。

因此,如果输入如下 s = “aolpeuvekyl”,则输出将为 5,因为回文是 “level”。

为了解决此问题,我们将按照以下步骤操作 -

  • n := s 的大小
  • 定义函数 dp()。它将获取 i、j
  • 如果 i 等于 j,则
    • 返回 1
  • 否则,当 i > j 时,则
    • 返回 0
  • 否则,
    • 如果 s[i] 等于 s[j],则
      • 返回 2 + dp(i + 1, j - 1)
    • 否则,
      • 返回 dp(i + 1, j) 和 dp(i, j - 1) 的最大值
  • 返回 dp(0, n - 1)

示例(Python)

让我们看看以下实现以获得更好的理解 -

 实时演示

class Solution:
   def solve(self, s):
      n = len(s)
      def dp(i, j):
         if i == j:
            return 1
         elif i > j:
            return 0
         else:
            if s[i] == s[j]:
               return 2 + dp(i + 1, j - 1)
            else:
               return max(dp(i + 1, j), dp(i, j - 1))
      return dp(0, n - 1)
ob = Solution()
s = "aolpeuvekyl"
print(ob.solve(s))

输入

"aolpeuvekyl"

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 年 12 月 12 日

724 次浏览

开启你的职业生涯

完成本课程获取认证

开始
广告