Python - หาความยาวลำดับคำนำหน้าที่ยาวที่สุดในอาร์เรย์คำ

โจทย์: กำหนดให้มีรายการคำ w (ตัวพิมพ์เล็กทั้งหมด) ต้องการหาความยาวของลำดับ (Sequence) ที่ยาวที่สุดที่แต่ละคำก่อนหน้าเป็น Prefix ของคำถัดไป และคำถัดไปมีเพียงตัวอักษรเดียวที่เพิ่มเข้ามา

ตัวอย่าง

Input: w = ["pqr", "pq", "m", "mn", "pqrs"]
Output: 3
เหตุผล: ลำดับ ["pq", "pqr", "pqrs"] ความยาว 3 (pq → pqr เพิ่ม 'r', pqr → pqrs เพิ่ม 's')

อัลกอริทึม: Dynamic Programming + Hash Map

ใช้ DP โดยที่ dp[word] = ความยาวลำดับที่ยาวที่สุดที่ลงท้ายด้วย word

ขั้นตอนการทำงาน

1. เรียงลำดับคำใน w (สำคัญ: ให้ Prefix มาก่อนคำที่ยาวกว่า)
2. สร้าง dp เป็น defaultdict(int) ค่าเริ่มต้น 0
3. วนลูปแต่ละ word ใน w ที่เรียงแล้ว:
   • dp[word] = dp[word[:-1]] + 1 (คำนำหน้าคือ word ตัดตัวสุดท้ายออก)
   • อัปเดตคำตอบสูงสุด

โค้ด Python

from collections import defaultdict

def solve(w):
    w.sort()  # เรียงให้ Prefix อยู่ก่อน
    dp = defaultdict(int)
    res = 0
    
    for word in w:
        # word[:-1] คือคำนำหน้า (Prefix) ที่ตัดตัวอักษรสุดท้ายออก
        dp[word] = dp[word[:-1]] + 1
        res = max(res, dp[word])
    
    return res

# ทดสอบ
w = ["pqr", "pq", "m", "mn", "pqrs"]
print(solve(w))  # Output: 3

การทำงานทีละขั้นตอน (Trace)

หลังเรียง: ["m", "mn", "pq", "pqr", "pqrs"]

ความซับซ้อน

• Time Complexity: O(n log n + n × L) โดย n = จำนวนคำ, L = ความยาวคำเฉลี่ย (จากการเรียงและ slicing)
• Space Complexity: O(n) สำหรับ Hash Map

ข้อสังเกต

• การเรียงลำดับ (Sort) สำคัญมาก เพราะรับประกันว่า Prefix จะถูกประมวลผลก่อนคำที่ยาวกว่า
• หากไม่เรียง อาจคำนวณ dp ผิด เพราะ Prefix ยังไม่ถูกคำนวณ
• โจทย์ระบุว่า "แต่ละคำก่อนหน้าเป็น Prefix ของคำถัดไป และเพิ่มแค่ 1 ตัวอักษร" ซึ่งตรงกับ word[:-1] อย่างสมบูรณ์