Today we will read on this article – Dictionary through Dictionary in C ++: If we want to find the longest string in the dictionary, it can be created by removing some letters of the given string. If there is more than one possible outcome, simply return the shortest term with lexicographic order. If there is no result, return an empty string. So if the input is like “abpcplea” and d = [“ale”, “apple”, “monkey”, “plea”], the result will be “apple”.

Example

#include <bits/stdc++.h>
using namespace std;
class program {
   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));
}

Input

"abpcplea"
["ade","apple","fox","green"]

Output

apple