โปรแกรมหาขนาด Common Special Subsequence ของสองสตริงใน Python

ให้สตริง s1, s2 หาความยาว Longest Common Subsequence (LCS) — "Special Subsequence" หมายถึง Subsequence (ลบตัวอักษรได้ 0 ตัวขึ้นไป)

ตัวอย่าง: s1='pineapple', s2='people' → 5 (LCS = "peple")

ขั้นตอน (DP Space Optimized O(min(m,n)))

1. ใช้ 2 Dictionary prev และ cur (Default 0)
2. วน i ทุกตัวอักษรใน s1:
   • วน j ทุกตัวอักษรใน s2:
     • cur[j] = prev[j-1]+1 if s1[i]==s2[j] else max(cur[j-1], prev[j])
   • prev = cur

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

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))  # Output: 5

อินพุต

'pineapple', 'people'

เอาต์พุต

5