मान लीजिए कि हमारे पास एक स्ट्रिंग और एक स्ट्रिंग डिक्शनरी है, हमें डिक्शनरी में सबसे लंबी स्ट्रिंग ढूंढनी है, जो दिए गए स्ट्रिंग के कुछ वर्णों को हटाकर बनाई जा सकती है। यदि एक से अधिक संभावित परिणाम हैं, तो बस सबसे छोटे शब्द को सबसे छोटे लेक्सिकोग्राफिक क्रम के साथ लौटाएं। यदि कोई परिणाम नहीं है, तो एक रिक्त स्ट्रिंग लौटाएं। इसलिए यदि इनपुट "abpcplea" और d =["ale", "apple", "Monkey", "plea"] जैसा है, तो परिणाम "सेब" होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- isSubsequence () नामक विधि को परिभाषित करें। इसमें s1 और s2 लगेंगे
- j :=0
- i के लिए 0 से s1 के आकार के बीच
- अगर s2[j] =s1[i], तो j को 1 से बढ़ाएं
- यदि j =s2 का आकार है, तो लूप तोड़ें
- सही लौटें अगर j =s2 का आकार
- मुख्य विधि से, निम्न कार्य करें -
- उत्तर:=एक खाली स्ट्रिंग
- i के लिए 0 से d – 1 के आकार के बीच
- x :=d[i]
- यदि x का आकार> उत्तर का आकार या x का आकार =उत्तर का आकार और x <उत्तर, तो
- यदि isSubsequence(s, x) सत्य है, तो उत्तर :=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