ধরুন আমাদের কাছে একটি ইংরেজি অভিধানের প্রতিনিধিত্বকারী শব্দের একটি তালিকা আছে, আমাদের প্রদত্ত শব্দ তালিকায় সবচেয়ে দীর্ঘতম শব্দটি খুঁজে বের করতে হবে যা শব্দের অন্যান্য শব্দ দ্বারা এক সময়ে একটি অক্ষর তৈরি করা যেতে পারে। যদি একাধিক সম্ভাব্য উত্তর থাকে, তাহলে সবচেয়ে ছোট লেক্সিকোগ্রাফিক্যাল ক্রম সহ দীর্ঘতম শব্দটি ফেরত দিন। যদি কোন উত্তর না থাকে, তাহলে খালি স্ট্রিং ফেরত দিন।
সুতরাং, যদি ইনপুটটি ["h","he","hel","hell", "hello"] এর মত হয়, তাহলে আউটপুট হবে "hello"
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- trie :=একটি নতুন মানচিত্র
- একটি ফাংশন সন্নিবেশ () সংজ্ঞায়িত করুন। এটি শব্দ গ্রহণ করবে
- এখন :=চেষ্টা করুন
- শব্দের প্রতিটি c-এর জন্য, করুন
- যদি এখন c না থাকে −
- now[c] ={'#', False}, তারপর
- এখন :=এখন[c]
- এখন['#'] :=সত্য
- যদি এখন c না থাকে −
- একটি ফাংশন অনুসন্ধান () সংজ্ঞায়িত করুন। এটি শব্দ গ্রহণ করবে
- এখন :=চেষ্টা করুন
- শব্দের প্রতিটি c-এর জন্য, করুন
- যদি '#' এখন এবং না এখন['#'] সত্য হয়, তাহলে
- মিথ্যে ফেরত দিন
- এখন :=এখন[c]
- এখনই ফিরুন['#']
- যদি '#' এখন এবং না এখন['#'] সত্য হয়, তাহলে
- শব্দে প্রতিটি শব্দের জন্য, করুন
- কল ইনসার্ট(শব্দ)
- উত্তর :=ফাঁকা স্ট্রিং
- শব্দে প্রতিটি শব্দের জন্য, করুন
- যদি অনুসন্ধান (শব্দ) এবং (শব্দের আকার> উত্তরের আকার বা (শব্দের আকার উত্তর এবং শব্দ <উত্তর) এর আকারের সমান হয়), তাহলে
- উত্তর :=শব্দ
- যদি অনুসন্ধান (শব্দ) এবং (শব্দের আকার> উত্তরের আকার বা (শব্দের আকার উত্তর এবং শব্দ <উত্তর) এর আকারের সমান হয়), তাহলে
- উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
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