Python - Tìm chuỗi tiền tố dài nhất trong mảng từ

Cho danh sách từ w (chữ thường), tìm độ dài chuỗi dài nhất mà mỗi từ là tiền tố của từ tiếp theo và từ tiếp theo chỉ thêm đúng 1 ký tự.

Ví dụ

Input: w = ["pqr", "pq", "m", "mn", "pqrs"]
Output: 3
Giải thích: Chuỗi ["pq", "pqr", "pqrs"] có độ dài 3.

Thuật toán: Quy hoạch động (DP) + Sắp xếp

1. Sắp xếp danh sách từ theo thứ tự từ điển (đảm bảo tiền tố đứng trước từ mở rộng)
2. Dùng dictionary dp lưu độ dài chuỗi dài nhất kết thúc tại từ đó
3. Với mỗi từ: dp[word] = dp[word[:-1]] + 1 (tiền tố bỏ ký tự cuối)
4. Theo dõi giá trị max

Mã Python

from collections import defaultdict

def solve(w):
    w.sort()  # Sắp xếp để tiền tố xuất hiện trước
    dp = defaultdict(int)
    res = 0
    
    for word in w:
        dp[word] = dp[word[:-1]] + 1
        res = max(res, dp[word])
    
    return res

# Test
w = ["pqr", "pq", "m", "mn", "pqrs"]
print(solve(w))  # Output: 3

Giải thích chi tiết

Sau khi sắp xếp: ["m", "mn", "pq", "pqr", "pqrs"]

• m: dp["m"] = dp[""] + 1 = 1
• mn: dp["mn"] = dp["m"] + 1 = 2
• pq: dp["pq"] = dp["p"] + 1 = 1 (vì "p" không có)
• pqr: dp["pqr"] = dp["pq"] + 1 = 2
• pqrs: dp["pqrs"] = dp["pqr"] + 1 = 3 ← max

Phân tích độ phức tạp

• Thời gian: O(n log n + n × L) - sắp xếp + duyệt (L = độ dài trung bình từ)
• Không gian: O(n × L) - lưu dictionary

Lưu ý: Sắp xếp là quan trọng để đảm bảo khi xử lý từ word, tiền tố word[:-1] đã được tính toán.