সমস্যা বিবরণ
একটি ডিকশনারি (শব্দের লিস্ট) দেওয়া থাকে। সেই শব্দটি খুঁজে বের করুন যা সবচেয়ে বড় এবং এক-এক অক্ষর করে অন্যান্য শব্দ থেকে তৈরি করা যায়। একাধিক হলে লেক্সিকোগ্রাফিক্যালি সবচেয়ে ছোটটি রিটার্ন করুন।
উদাহরণ
words = ["h","he","hel","hell","hello"] → আউটপুট: "hello"
"h" → "he" → "hel" → "hell" → "hello" — প্রতিটি প্রিফিক্স ডিকশনারিতে আছে।
এলগরিদম (Trie + DFS)
- একটি Trie (প্রিফিক্স ট্রি) তৈরি করুন যেখানে প্রতিটি নোডে
'#'কী দিয়ে শব্দের শেষ চিহ্নিত করুন। - সব শব্দ Trie-এ ইনসার্ট করুন।
- প্রতিটি শব্দের জন্য সার্চ করুন: প্রতিটি প্রিফিক্সে
'#'= True কিনা চেক করুন। - বৈধ শব্দগুলোর মধ্যে সবচেয়ে বড়টি, টাই হলে লেক্সিকোগ্রাফিক্যালি ছোটটি বেছে নিন।
পাইথন বাস্তবায়ন
class Solution:
def longestWord(self, words):
trie = {}
END = '#'
def insert(word):
node = trie
for c in word:
node = node.setdefault(c, {})
node[END] = True
def search(word):
node = trie
for c in word:
if END not in node or not node[END]:
return False
node = node[c]
return END in node and node[END]
for w in words:
insert(w)
ans = ""
for w in words:
if search(w) and (len(w) > len(ans) or (len(w) == len(ans) and w < ans)):
ans = w
return ans
ob = Solution()
print(ob.longestWord(["h","he","hel","hell","hello"])) # helloইনপুট / আউটপুট
ইনপুট: ["h","he","hel","hell","hello"] আউটপুট: hello
