สมมติว่าเรามีสองสตริง s1 และ s2 เราต้องหาขนาดของสตริงที่ยาวที่สุด s3 ซึ่งเป็นสตริงย่อยพิเศษของทั้ง s1 และ s2
เราสามารถพูดได้ว่าสตริง x เป็นสตริงย่อยพิเศษของสตริง y อื่น หากสามารถสร้าง x ได้โดยการลบอักขระ 0 ตัวขึ้นไปจาก y
ดังนั้น หากอินพุตเป็นเหมือน s1 ='pineapple' s2 ='people' ผลลัพธ์จะเป็น 5 เนื่องจากสตริงย่อยพิเศษคือ 'peple' ขนาด 5
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- prev :=พจนานุกรมใหม่ ซึ่งหากไม่มีคีย์บางคีย์ ให้คืนค่า 0
- สำหรับ i ในช่วง 0 ถึงขนาด s1 - 1 ให้ทำ
- cur :=พจนานุกรมใหม่ ซึ่งหากไม่มีคีย์บางคีย์ ให้คืนค่า 0
- สำหรับ j ในช่วง 0 ถึงขนาด s2- 1 ให้ทำ
- cur[j] :=prev[j - 1] + 1 เมื่อ s1[i] เหมือนกับ s2[j] มิฉะนั้น ค่าสูงสุดของ cur[j -1] และ prev[j]
- ก่อนหน้า :=cur
- ส่งคืนก่อนหน้า[ขนาดของ s2 -1]
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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))
อินพุต
'pineapple', 'people'
ผลลัพธ์
5
