在 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矩阵
对于范围在1到m的i，执行以下操作：
- 对于范围在1到n的j，执行以下操作：
  - 对于范围在1到o的k，执行以下操作：
  - 如果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相关文章，请阅读：Python 教程

示例（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))