ধরুন আমাদের একটি স্ট্রিং এবং একটি স্ট্রিং ডিকশনারি আছে, আমাদের ডিকশনারিতে সবচেয়ে বড় স্ট্রিং খুঁজে বের করতে হবে যা দেওয়া স্ট্রিং-এর কিছু অক্ষর ডিলিট করে তৈরি করা যায়। যদি একাধিক সম্ভাব্য ফলাফল থাকে, তবে সর্বোচ্চ দৈর্ঘ্যের শব্দটি ফেরত দিন যার লেক্সিকোগ্রাফিক্যাল অর্ডার সবচেয়ে ছোট। যদি কোন ফলাফল না থাকে, তবে খালি স্ট্রিং ফেরত দিন। তাই যদি ইনপুট হয় “abpcplea” এবং d = [“ale”, “apple”, “monkey”, “plea”], তবে ফলাফল হবে “apple”।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- isSubsequence() নামে একটি মেথড সংজ্ঞায়িত করুন। এটি s1 এবং s2 নেবে
- j := ০
- i = 0 থেকে s1-এর আকার পর্যন্ত
- যদি s2[j] = s1[i], তবে j ১ বৃদ্ধি করুন
- যদি j = s2-এর আকার হয়, তবে লুপ ভাঙুন
- যদি j = s2-এর আকার হয় তবে true ফেরত দিন
- মূল মেথড থেকে, নিম্নলিখিত কাজ করুন −
- ans := একটি খালি স্ট্রিং
- i = 0 থেকে d-এর আকার – ১ পর্যন্ত
- x := d[i]
- যদি x-এর আকার > ans-এর আকার বা x-এর আকার = ans-এর আকার এবং x < ans, তবে
- যদি isSubsequence(s, x) true হয়, তবে ans := x
- ret ফেরত দিন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −
উদাহরণ
#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
