Chương trình tìm độ dài chuỗi con đặc biệt chung dài nhất của hai chuỗi trong Python

Cho hai chuỗi s1 và s2. Chuỗi x là "chuỗi con đặc biệt" của y nếu x có thể tạo được bằng cách xóa 0 hoặc nhiều ký tự từ y (tức là subsequence). Tìm độ dài chuỗi con đặc biệt chung dài nhất (Longest Common Subsequence - LCS).

Ví dụ: s1 = 'pineapple', s2 = 'people' → kết quả 5 (chuỗi con: 'peple').

Thuật toán giải quyết (Dynamic Programming O(n×m))

1. Dùng defaultdict(int) cho hàng trước (prev) và hàng hiện tại (cur)
2. Duyệt i qua s1, j qua s2:
   • Nếu s1[i] == s2[j]: cur[j] = prev[j-1] + 1
   • Ngược lại: cur[j] = max(cur[j-1], prev[j])
3. Cập nhật prev = cur sau mỗi hàng
4. Trả về prev[len(s2)-1]

Ví dụ minh họa

from collections import defaultdict

def solve(s1, s2):
    prev = defaultdict(int)
    for i in range(len(s1)):
        cur = defaultdict(int)
        for j in range(len(s2)):
            cur[j] = prev[j-1] + 1 if s1[i] == s2[j] else max(cur[j-1], prev[j])
        prev = cur
    return prev[len(s2)-1]

s1 = 'pineapple'
s2 = 'people'
print(solve(s1, s2))

Đầu vào

'pineapple', 'people'

Đầu ra

5