Python程序:查找三个字符串的最长公共子序列长度


假设我们有三个字符串 s1、s2 和 s3,我们需要找到它们的最长公共子序列的长度。

例如,如果输入是 s1 = "ababchemxde" s2 = "pyakcimde" s3 = "oauctime",则输出为 4,因为最长公共子序列是 "acme"。

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

  • m := s1 的长度,n := s2 的长度,o := s3 的长度
  • dp := 一个大小为 (o + 1) x (n + 1) x (m + 1) 的 3D 矩阵
  • 对于 i 从 1 到 m,执行:
    • 对于 j 从 1 到 n,执行:
      • 对于 k 从 1 到 o,执行:
        • 如果 s1[i - 1]、s2[j - 1]、s3[k - 1] 相同,则
          • dp[i, j, k] := 1 + dp[i - 1, j - 1, k - 1]
        • 否则,
          • dp[i, j, k] = dp[i - 1, j, k]、dp[i, j - 1, k] 和 dp[i, j, k - 1] 的最大值
  • 返回 dp[m, n, o]

示例 (Python)

让我们看看下面的实现来更好地理解:

 在线演示

class Solution:
   def solve(self, s1, s2, s3):
      m = len(s1)
      n = len(s2)
      o = len(s3)
      dp = [[[0 for i in range(o + 1)] for j in range(n + 1)] for k in range(m + 1)]
      for i in range(1, m + 1):
         for j in range(1, n + 1):
            for k in range(1, o + 1):
               if s1[i - 1] == s2[j - 1] == s3[k - 1]:
                  dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1]
               else:
                  dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
         return dp[m][n][o]
ob = Solution()
s1 = "ababchemxde"
s2 = "pyakcimde"
s3 = "oauctime"
print(ob.solve(s1, s2, s3))

输入

"ababchemxde", "pyakcimde", "oauctime"

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

输出

4

更新于:2020年12月12日

604 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告