पायथन में एक शब्द सरणी की सबसे लंबी उपसर्ग अनुक्रम खोजने का कार्यक्रम

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• सूची को क्रमबद्ध करें
• 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