पायथन में वर्ड ऐरे के सबसे लंबे प्रीफिक्स सीक्वेंस की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास w नामक शब्दों की एक सूची है, जिसमें लोअरकेस स्ट्रिंग्स हैं। हमें w के सबसे लंबे सीक्वेंस की लंबाई ढूंढनी है जहां प्रत्येक पिछला शब्द अगले शब्द का प्रीफिक्स है और अगले शब्द में केवल एक नया कैरेक्टर जुड़ा हुआ है।

उदाहरण के लिए, यदि इनपुट है w = ["pqr", "pq", "m", "mn", "pqrs"], तो आउटपुट 3 होगा क्योंकि हमें सीक्वेंस ["pq", "pqr", "pqrs"] मिल सकता है, जिसकी लंबाई 3 है।

एल्गोरिदम

1. सूची w को सॉर्ट करें।
2. dp := एक मैप, जहां किसी कुंजी का डिफ़ॉल्ट मान 0 है।
3. res := 0
4. प्रत्येक word के लिए w में:
   • dp[word] := dp[word[:-1]] + 1
   • res := max(res, dp[word])
5. res लौटाएं

उदाहरण कार्यान्वयन

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))  # आउटपुट: 3

इनपुट

["pqr", "pq", "m", "mn", "pqrs"]

आउटपुट

3