মান লেযিয়ে আমাদের শব্দের একটি তালিকা আছে, যেখানে প্রতিটি শব্দ ছোট হাতের অক্ষর দিয়ে গঠিত। একটি শব্দ word1 অন্য শব্দ word2-এর predecessor (পূর্ববর্তি) হবে যদি এবং কেবল যদি word1-এ ঠিক একটি অক্ষর যেকোনো স্থানে যোগ করে word2 তৈরি করা যায়। উদাহরণস্বরূপ, "abc" হল "abac"-এর predecessor। এখন একটি শব্দ চেইন হল শব্দের একটি সিকোয়েন্স [word_1, word_2, ..., word_k] যেখানে k ≥ 1, এবং word_1 হল word_2-এর predecessor, word_2 হল word_3-এর predecessor, ইত্যাদি। প্রদত্ত শব্দ তালিকা থেকে সবচেয়ে লম্বা শব্দ চেইনের দৈর্ঘ্য খুঁজে বের করতে হবে।
যদি ইনপুট হয়: ["a","b","ba","bca","bda","bdca"], তবে ফলাফল হবে ৪, কারণ সবচেয়ে লম্বা চেইনগুলির একটি হল ["a", "ba", "bda", "bdca"]।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
একটি dp ম্যাপ সংজ্ঞায়িত করুন, n := words অ্যারের আকার
words অ্যারেটি দৈর্ঘ্য অনুযায়ী সর্ট করুন
ret := 0
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
best := 0
j = 0 থেকে words[i].size()-1 পর্যন্ত লুপ চালান
word := (words[i]-র 0 থেকে j-1 পর্যন্ত সাবস্ট্রিং) + (words[i]-র j+1 থেকে শেষ পর্যন্ত সাবস্ট্রিং)
best := max(best, dp[word] + 1)
dp[words[i]] := best
ret := max(ret, dp[words[i]])
return ret
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: static bool cmp(string s1, string s2){ return s1.size() < s2.size(); } int longestStrChain(vector<string>& words) { unordered_map <string, int> dp; int n = words.size(); sort(words.begin(), words.end(), cmp); int ret = 0; for(int i = 0; i < n; i++){ int best = 0; for(int j = 0; j < words[i].size(); j++){ string word = words[i].substr(0, j) + words[i].substr(j + 1); best = max(best, dp[word] + 1); } dp[words[i]] = best; ret = max(ret, dp[words[i]]); } return ret; } }; main(){ vector<string> v = {"a","b","ba","bca","bda","bdca"}; Solution ob; cout << (ob.longestStrChain(v)); }ইনপুট
["a","b","ba","bca","bda","bdca"]
আউটপুট
4
