Chương trình Python tìm số phép xóa tối thiểu để hai chuỗi bằng nhau

Cho hai chuỗi s, t. Phép toán: xóa 1 ký tự bất kỳ từ một trong hai chuỗi. Tìm số phép xóa tối thiểu để s == t.

Ví dụ

Input: s = "pipe", t = "ripe"

Output: 2

Giải thích: Xóa 'p' từ s và 'r' từ t → cả hai thành "ipe".

Thuật toán (DP - Longest Common Subsequence)

Số phép xóa tối thiểu = len(s) + len(t) - 2 * LCS(s, t).
Đề bài dùng đệ quy + memoization (top-down DP) tính trực tiếp:

• dp(i, j): số phép xóa tối thiểu từ s[i:] và t[j:].
• Nếu i == len(s) → xóa hết t[j:]: trả về len(t) - j.
• Nếu j == len(t) → xóa hết s[i:]: trả về len(s) - i.
• Nếu s[i] == t[j] → giữ lại, gọi dp(i+1, j+1).
• Ngược lại → xóa s[i] hoặc t[j]: 1 + min(dp(i+1, j), dp(i, j+1)).

Mã nguồn Python

from functools import lru_cache

def solve(s, t):
    m, n = len(s), len(t)

    @lru_cache(None)
    def dp(i, j):
        if i == m:
            return n - j
        if j == n:
            return m - i
        if s[i] == t[j]:
            return dp(i + 1, j + 1)
        return 1 + min(dp(i + 1, j), dp(i, j + 1))

    return dp(0, 0)

# Test
s = "pipe"
t = "ripe"
print(solve(s, t))  # Output: 2

Độ phức tạp

• Thời gian: O(m*n) với memoization.
• Không gian: O(m*n) cho cache.

Lưu ý: Bài toán tương đương tìm LCS (Longest Common Subsequence).