โปรแกรมหาความยาวของลำดับย่อยร่วมที่ยาวที่สุดของสามสตริงใน Python

สมมติว่าเรามีสตริงสามตัว s1, s2, s3 เราต้องการหาความยาวของลำดับย่อยร่วม (common subsequence) ที่ยาวที่สุดของทั้งสาม

เช่น ถ้าข้อมูลนำเข้าคือ s1 = "ababchemxde", s2 = "pyakcimde", s3 = "oauctime" ผลลัพธ์จะเป็น 4 เนื่องจากลำดับย่อยร่วมยาวที่สุดคือ "acme"

ขั้นตอนการแก้ปัญหา (3D Dynamic Programming)

• m := len(s1), n := len(s2), o := len(s3)
• dp := 3D matrix ขนาด (m+1) x (n+1) x (o+1)
• วน 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] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])
• คืน dp[m][n][o]

ตัวอย่างโค้ด

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"

ผลลัพธ์

4