สมมติว่าเรามีรายการคำที่เรียกว่า w พร้อมสตริงตัวพิมพ์เล็ก เราต้องหาความยาวของลำดับที่ยาวที่สุดของ w โดยที่คำก่อนหน้าแต่ละคำเป็นคำนำหน้าของคำถัดไป และคำถัดไปมีอักขระใหม่เพียงตัวเดียวต่อท้าย
ดังนั้น หากอินพุตเป็น w =["pqr", "pq", "m", "mn", "pqrs"] ผลลัพธ์จะเป็น 3 เพราะเราสามารถรับลำดับ:["pq", " pqr", "pqrs"] ซึ่งมีความยาวเท่ากับ 3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เรียงลำดับรายการ w
- dp :=แผนที่ โดยค่าเริ่มต้นสำหรับคีย์คือ 0
- res :=0
- สำหรับแต่ละคำใน w ทำ
- dp[word] :=dp[สตริงย่อยของคำจนถึงองค์ประกอบสุดท้ายที่สอง] + 1
- res :=สูงสุดของ res และ dp[word]
- ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
from collections import defaultdict def solve(w): w.sort() dp = defaultdict(int) res = 0 for word in w: dp[word] = dp[word[:-1]] + 1 res = max(res, dp[word]) return res w = ["pqr", "pq", "m", "mn", "pqrs"] print(solve(w))
อินพุต
["pqr", "pq", "m", "mn", "pqrs"]
ผลลัพธ์
3
