Chương trình tìm độ dài của dãy con chung dài nhất của ba chuỗi trong Python

Giả sử chúng ta có ba chuỗi s1, s2 và s3, chúng ta phải tìm độ dài của dãy con chung dài nhất của chúng.

Vì vậy, nếu đầu vào giống như s1 ="ababchemxde" s2 ="pyakcimde" s3 ="oauctime", thì đầu ra sẽ là 4, vì dãy con chung dài nhất là "acme".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=kích thước của s1, n:=kích thước của s2, o:=kích thước của s3
• dp:=ma trận 3D có kích thước (o + 1) x (n + 1) x (m + 1)
• đối với tôi trong phạm vi từ 1 đến m, hãy thực hiện
  • đối với j trong phạm vi từ 1 đến n, thực hiện
    • đối với k trong phạm vi từ 1 đến o, thực hiện
      • nếu s1 [i - 1], s2 [j - 1], s3 [k - 1] giống nhau thì
        • dp [i, j, k]:=1 + dp [i - 1, j - 1, k - 1]
      • nếu không,
        • dp [i, j, k] =tối đa của (dp [i - 1, j, k], dp [i, j - 1, k] và dp [i, j, k - 1])
• trả về dp [m, n, o]

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

"ababchemxde", "pyakcimde", "oauctime"

Đầu ra

4