पायथन में शब्दकोश में सबसे लंबा शब्द

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

उदाहरण के लिए, यदि इनपुट ["h","he","hel","hell", "hello"] है, तो आउटपुट "hello" होगा।

हल करने के चरण

trie := एक नया मैप
insert() फ़ंक्शन परिभाषित करें। यह word लेगा
- now := trie
- word में प्रत्येक c के लिए:
  - यदि c now में नहीं है, तो now[c] = {'#': False}
  - now := now[c]
  - now['#'] := True
search() फ़ंक्शन परिभाषित करें। यह word लेगा
- now := trie
- word में प्रत्येक c के लिए:
  - यदि '#' now में है और now['#'] True नहीं है, तो False वापस करें
  - now := now[c]
  - now['#'] वापस करें
words में प्रत्येक word के लिए insert(word) कॉल करें
ans := खाली स्ट्रिंग
words में प्रत्येक word के लिए:
- यदि search(word) और (word की लंबाई > ans की लंबाई या (word की लंबाई == ans की लंबाई और word < ans)), तो:
  - ans := word
ans वापस करें

उदाहरण

class Solution:
    def longestWord(self, words):
        self.trie = {}
        def insert(word):
            now = self.trie
            for c in word:
                if c not in now:
                    now[c] = {'#': False}
                now = now[c]
            now['#'] = True
        def search(word):
            now = self.trie
            for c in word:
                if '#' in now and not now['#']:
                    return False
                now = now[c]
            return now['#']
        for word in words:
            insert(word)
        ans = ""
        for word in words:
            if (search(word) and (len(word) > len(ans) or (len(word) == len(ans) and word < ans))):
                ans = word
        return ans

ob = Solution()
print(ob.longestWord(["h","he","hel","hell", "hello"]))

इनपुट

["h","he","hel","hell", "hello"]

आउटपुट

hello