C++-এ মিলিত অনুক্রমের সংখ্যা

ধরুন আমাদের কাছে একটি স্ট্রিং S এবং শব্দের শব্দের অভিধান আছে, শব্দের সংখ্যা [i] খুঁজে বের করুন যা S-এর একটি অনুগামী। তাই যদি ইনপুট হয় S="abcde" এবং অভিধানটি হয় [“a”, “bb”, “acd”, “ace”], তাহলে আউটপুট হবে 3। কারণ অভিধানে তিনটি ক্রম আছে, যেগুলো S-এর পরবর্তি শব্দ:“a” “acd” এবং “ace”

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=শব্দ বিন্যাসের আকার
একটি মানচিত্র তৈরি করুন m
আমি 0 থেকে শব্দের আকারের মধ্যে
- শব্দ[i] সন্নিবেশ করান
উত্তর :=0
আমি 0 থেকে S
- char x :=S[i]
- যদি x ম্যাপে m থাকে, তাহলে
  - temp :=m[x], এবং m[x] মুছুন
  - 0 থেকে টেম্প সাইজের মধ্যে j এর জন্য
    - যদি temp[j] =1 এর আকার হয়, তাহলে উত্তর 1 দ্বারা বাড়ান, অন্যথায় সূচক 1 থেকে m[temp[j, 1]] এ টেম্প[j]-এর সাবস্ট্রিং সন্নিবেশ করান
উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int numMatchingSubseq(string S, vector<string>& words) {
      int n = words.size();
      map <char, vector <string> > m;
      for(int i = 0; i < words.size(); i++){
         m[words[i][0]].push_back(words[i]);
      }
      int ans = 0;
      for(int i = 0; i < S.size(); i++){
         char x = S[i];
         if(m.find(x) != m.end()){
            vector <string> temp = m[x];
            m.erase(x);
            for(int j = 0; j < temp.size(); j++){
               if(temp[j].size() == 1){
                  ans++;
               } else {
                  m[temp[j][1]].push_back(temp[j].substr(1));
               }
            }
         }
      }
      return ans;
   }
};
int main() {
   Solution ob1;
   string s = "abcde";
   vector<string> v{"a","bb","acd","ace"};
   cout << ob1.numMatchingSubseq(s, v) << endl;
   return 0;
}

ইনপুট

"abcde"
["a","bb","acd","ace"]
string s = "abcde";
vector<string> v{"a","bb","acd","ace"};