C++ এ স্ট্রিং গঠনের সংক্ষিপ্ততম উপায়

ধরুন আমাদের একটি স্ট্রিং আছে, আমরা কিছু সংখ্যক অক্ষর মুছে দিয়ে সেই স্ট্রিংটির একটি অনুগামী গঠন করতে পারি (সম্ভবত কোনো মুছে ফেলা হয়নি)। সুতরাং যদি দুটি স্ট্রিং উত্স এবং লক্ষ্য থাকে, তবে আমাদের উত্সের ন্যূনতম সংখ্যক অনুবর্তনগুলি খুঁজে বের করতে হবে যাতে তাদের সংযোজন লক্ষ্যের সমান হয়। যদি কাজটি অসম্ভব হয়, তাহলে -1 ফেরত দিন। সুতরাং উৎস যদি হয় "abc" এবং লক্ষ্য "abcbc" হয়, তাহলে আউটপুট হবে 2।

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

• সম্ভব নামক একটি স্ট্রিং সংজ্ঞায়িত করুন, এটি s এবং t ইনপুট হিসাবে গ্রহণ করবে

• একটি মানচিত্র তৈরি করুন m

• প্রতিটি অক্ষরের জন্য c s চিহ্ন m[c] :=1

• t-এ প্রতিটি অক্ষরের জন্য c, যদি m[c] 0 হয়, তাহলে মিথ্যা ফেরত দিন

• প্রত্যাবর্তন সত্য

• এখন মূল পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• ssz :=s এর আকার এবং tsz :=t এর আকার

• ক্যারেক্টার টাইপ কী এবং অ্যারে টাইপ ভ্যালুর একটি ম্যাপ m তৈরি করুন

• আমি 0 থেকে ssz

  পরিসরে

  • m[s[i]]

    -এ i ঢোকান

• pre :=-1 এবং ret :=1

• আমি 0 থেকে tsz

  পরিসরে

  • যদি t[i] m-এ উপস্থিত না থাকে, তাহলে -1

    ফেরত দিন

  • v :=m[t[i]]

  • সেট i :=v এ উপাদানের সূচী, যা প্রাক

    থেকে বড়

  • যদি আমি তালিকার শেষ না হয়

    • ret 1 দ্বারা বৃদ্ধি করুন এবং pre :=v[0]

  • অন্যথায় পূর্বে :=v[i]

• রিটার্ন রিটার্ন

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool possible(string s, string t){
      map <char, int> m;
      for(int i = 0; i < s.size(); i++){
         m[s[i]] = 1;
      }
      for(int i = 0; i < t.size(); i++){
         if(!m[t[i]])return false;
      }
      return true;
   }
   int shortestWay(string s, string t) {
      int ssz = s.size();
      int tsz = t.size();
      map <char, vector <int> > m;
      for(int i = 0; i < ssz; i++){
         m[s[i]].push_back(i);
      }
      int pre = -1;
      int ret = 1;
      for(int i = 0; i < tsz; i++){
         if(!m.count(t[i]))return -1;
         vector <int>& v = m[t[i]];
         vector <int> :: iterator it = upper_bound(v.begin(),
         v.end(), pre);
         if(it == v.end()){
            ret++;
            pre = v[0];
         }else{
            pre = *it;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.shortestWay("abc", "abcbc"));
}

ইনপুট

"abc"
"abcbc"

আউটপুট

2