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

คำอธิบายปัญหา

กำหนดสตริง s, t อนุญาตลบตัวอักษรจากสตริงใดก็ได้ หาจำนวนการลบน้อยที่สุดทำให้ s == t

ตัวอย่าง

s = "pipe", t = "ripe" → Output: 2

ลบ 'p' จาก s, ลบ 'r' จาก t → ทั้งคู่กลายเป็น "ipe"

ขั้นตอนการแก้ปัญหา (DP - LCS Variant)

1. DP(i,j) = การลบน้อยสุดจาก s[i:], t[j:]
2. ถ้า s[i] == t[j]: DP(i+1, j+1)
3. มิฉะนั้น: 1 + min(DP(i+1,j), DP(i,j+1)) (ลบจาก s หรือ t)
4. Base case: หมดสตริง → ลบอีกอันหมด

เทียบเท่ากับ len(s) + len(t) - 2*LCS(s,t)

การตนการทำงาน (Python)

def solve(s, t):
    m, n = len(s), len(t)
    def dp(i, j):
        if i == m:
            return n - j
        elif j == n:
            return m - i
        else:
            if s[i] == t[j]:
                return dp(i + 1, j + 1)
            else:
                return 1 + min(dp(i + 1, j), dp(i, j + 1))
    return dp(0, 0)

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

อินพุต / เอาต์พุต

Input:  "pipe", "ripe"
Output: 2