C++ में विलोपन के माध्यम से शब्दकोश में सबसे लंबा शब्द

मान लीजिए हमारे पास एक स्ट्रिंग और एक स्ट्रिंग शब्दकोश है, हमें शब्दकोश में सबसे लंबी स्ट्रिंग ढूंढनी है जिसे दी गई स्ट्रिंग के कुछ वर्णों को हटाकर बनाया जा सकता है। यदि एक से अधिक संभावित परिणाम हैं, तो सबसे छोटे शब्दकोश क्रम वाले सबसे लंबे शब्द को लौटाएं। यदि कोई परिणाम नहीं है, तो एक खाली स्ट्रिंग लौटाएं। इसलिए यदि इनपुट "abpcplea" और d = ["ale", "apple", "monkey", "plea"] है, तो परिणाम "apple" होगा।

हल का दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• isSubsequence() नामक एक विधि परिभाषित करें। यह s1 और s2 लेगा
  • j := 0
  • i = 0 से s1 का आकार तक:
    • यदि s2[j] = s1[i], तो j को 1 से बढ़ाएं
    • यदि j = s2 का आकार, तो लूप तोड़ें
  • यदि j = s2 का आकार तो true लौटाएं
• मुख्य विधि से, निम्नलिखित करें:
  • ans := एक खाली स्ट्रिंग
  • i = 0 से d का आकार - 1 तक:
    • x := d[i]
    • यदि x का आकार > ans का आकार या x का आकार = ans का आकार और x < ans:
      • यदि isSubsequence(s, x) true है, तो ans := x
  • ans लौटाएं

उदाहरण

#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; 
    } 
}; 

int main(){ 
    vector<string> v = {"ale","apple","monkey","plea"}; 
    Solution ob; 
    cout << (ob.findLongestWord("abpcplea", v)); 
}

इनपुट

"abpcplea" ["ale","apple","monkey","plea"]

आउटपुट

apple