ধরুন আমাদের কাছে শব্দের একটি তালিকা আছে, এখানে প্রতিটি শব্দ ছোট হাতের অক্ষর নিয়ে গঠিত। সুতরাং একটি শব্দ word1 হল আরেকটি শব্দ word2-এর পূর্বসূরি যদি এবং শুধুমাত্র যদি আমরা word1-এর যেকোনো জায়গায় ঠিক একটি অক্ষর যোগ করতে পারি যাতে এটি word2 এর সমান হয়। পূর্বসূরির উদাহরণের মতো, "abc" হল "abac" এর পূর্বসূরী। এখন একটি শব্দ শৃঙ্খল হল শব্দের একটি ক্রম [word_1, word_2, ..., word_k] সঙ্গে k>=1, যেখানে word_1 হল word_2 এর পূর্বসূরি, word_2 হল word_3 এর পূর্বসূরি, ইত্যাদি। প্রদত্ত শব্দের তালিকা থেকে বেছে নেওয়া শব্দগুলির সাহায্যে আমাদের একটি শব্দ শৃঙ্খলের দীর্ঘতম সম্ভাব্য দৈর্ঘ্য খুঁজে বের করতে হবে।
সুতরাং যদি ইনপুটটি এরকম হয়:["a","b","ba","bca","bda","bdca"], তাহলে ফলাফল হবে 4, কারণ দীর্ঘতম চেইনের একটি হবে [“ a”, “ba”, “bda”, “bdca”]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি মানচিত্র dp সংজ্ঞায়িত করুন, n :=শব্দ বিন্যাসের আকার
-
দৈর্ঘ্যের উপর ভিত্তি করে শব্দ বিন্যাস সাজান
-
ret :=0
-
আমি 0 tn n – 1
পরিসরে-
সেরা :=0
-
j-এর জন্য রেঞ্জ 0 থেকে শব্দের দৈর্ঘ্য [i] – 1
-
শব্দ :=(শব্দের সাবস্ট্রিং[i] 0 থেকে j – 1) সংযুক্ত (শব্দের সাবস্ট্রিং [i] j + 1 থেকে শেষ পর্যন্ত)
-
সেরা :=সেরার সর্বোচ্চ, dp[শব্দ] + 1
-
-
dp[words[i]] :=সেরা
-
ret :=সর্বাধিক (ret, dp[words[i]])
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
