Giả sử chúng ta có một danh sách các từ được gọi là w, với các chuỗi chữ thường. Chúng ta phải tìm độ dài của dãy w dài nhất trong đó mỗi từ trước đó là tiền tố của từ tiếp theo và từ tiếp theo chỉ có một ký tự mới được thêm vào.
Vì vậy, nếu đầu vào là w =["pqr", "pq", "m", "mn", "pqrs"], thì đầu ra sẽ là 3 vì chúng ta có thể nhận được chuỗi:["pq", " pqr "," pqrs "], có độ dài là 3.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- sắp xếp danh sách w
- dp:=một bản đồ, trong đó giá trị mặc định cho khóa là 0
- res:=0
- đối với mỗi từ trong w, thực hiện
- dp [word]:=dp [chuỗi con của từ lên đến phần tử cuối cùng thứ hai] + 1
- res:=tối đa là res và dp [word]
- trả lại res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
["pqr", "pq", "m", "mn", "pqrs"]
Đầu ra
3