ধরুন আমাদের একটি স্ট্রিং এবং একটি স্ট্রিং অভিধান আছে, আমাদের অভিধানে দীর্ঘতম স্ট্রিংটি খুঁজে বের করতে হবে যেটি প্রদত্ত স্ট্রিংয়ের কয়েকটি অক্ষর মুছে ফেলার মাধ্যমে তৈরি করা যেতে পারে। যদি একাধিক সম্ভাব্য ফলাফল থাকে, তাহলে সবচেয়ে ছোট শব্দকোষের ক্রম সহ দীর্ঘতম শব্দটি ফেরত দিন। যদি কোন ফলাফল না থাকে, তাহলে একটি ফাঁকা স্ট্রিং ফেরত দিন। তাই যদি ইনপুট হয় “abpcplea” এবং d =[“ale”, “apple”, “monkey”, “plea”], তাহলে ফলাফল হবে “apple”।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- isSubsequence() নামে একটি পদ্ধতি সংজ্ঞায়িত করুন। এটি s1 এবং s2 নিবে
- j :=0
- আমি 0 থেকে s1
- এর পরিসরে
- যদি s2[j] =s1[i] হয়, তাহলে j 1 দ্বারা বাড়ান
- যদি j =s2 এর সাইজ হয়, তাহলে লুপ ভাঙ্গুন
j =s2 এর আকার হলে - সত্য ফেরত দিন
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
- উত্তর :=একটি ফাঁকা স্ট্রিং
- আমি 0 থেকে d – 1
- এর পরিসরে
- x :=d[i]
- যদি x এর সাইজ> ans এর সাইজ বা x =ans এর সাইজ এবং x
- যদি সাবসকোয়েন্স(s, x) সত্য হয়, তাহলে ans :=x
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isSubsequence(string s1, string s2){
int j =0;
for(int i = 0; i < s1.size(); i++){
if(s2[j] == s1[i]){
j++;
if(j == s2.size()) break;
}
}
return j == s2.size();
}
string findLongestWord(string s, vector<string>& d) {
string ans = "";
for(int i = 0; i < d.size(); i++){
string x = d[i];
if(x.size() > ans.size() || (x.size() == ans.size() && (x < ans))){
if(isSubsequence(s, x)) ans = x;
}
}
return ans;
}
};
main(){
vector<string> v = {"ale","apple","monkey","plea"};
Solution ob;
cout << (ob.findLongestWord("abpcplea", v));
} ইনপুট
"abpcplea" ["ale","apple","monkey","plea"]
আউটপুট
apple
