Chương trình tìm độ dài chuỗi supersequence ngắn nhất trong Python

Cho hai chuỗi s và t. Ta cần tìm độ dài của chuỗi ngắn nhất mà cả s và t đều là các dãy con (subsequence) của nó.

Ví dụ, nếu đầu vào là s = "pipe", t = "people", thì kết quả là 7, vì một supersequence có thể là "pieople".

Giải thuật

1. Gán m = len(s), n = len(t).
2. Tạo bảng DP kích thước (m+1) x (n+1) khởi tạo bằng 0.
3. Duyệt i từ 0 đến m, j từ 0 đến n:
   • Nếu i == 0 hoặc j == 0: table[i][j] = 0.
   • Ngược lại, nếu s[i-1] == t[j-1]: table[i][j] = 1 + table[i-1][j-1].
   • Khác: table[i][j] = max(table[i][j-1], table[i-1][j]).
4. Kết quả: m + n - table[m][n] (tổng độ dài trừ độ dài LCS).

Ví dụ minh họa

class Solution:
    def solve(self, s, t):
        m = len(s)
        n = len(t)
        table = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 or j == 0:
                    table[i][j] = 0
                elif s[i - 1] == t[j - 1]:
                    table[i][j] = 1 + table[i - 1][j - 1]
                else:
                    table[i][j] = max(table[i][j - 1], table[i - 1][j])
        return m + n - table[m][n]

ob = Solution()
s = "pipe"
t = "people"
print(ob.solve(s, t))  # Output: 7

Đầu vào / Đầu ra

Input: "pipe", "people"

Output: 7