सी ++ में स्ट्रिंग बनाने का सबसे छोटा तरीका

मान लीजिए कि हमारे पास एक स्ट्रिंग है, हम कुछ वर्णों को हटाकर उस स्ट्रिंग का एक क्रम बना सकते हैं (संभवतः कोई विलोपन नहीं)। इसलिए यदि दो तार स्रोत और लक्ष्य हैं, तो हमें स्रोत के बाद के अनुक्रमों की न्यूनतम संख्या ज्ञात करनी होगी जैसे कि उनका संयोजन लक्ष्य के बराबर हो। यदि कार्य असंभव है, तो -1 लौटें। तो अगर स्रोत “abc” है और लक्ष्य “abcbc” है, तो आउटपुट 2 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• संभव नामक एक स्ट्रिंग को परिभाषित करें, यह इनपुट के रूप में s और t लेगा

• एक नक्शा बनाएं मी

• प्रत्येक वर्ण c के लिए s चिह्न m[c] :=1

• t में प्रत्येक वर्ण c के लिए, यदि m[c] 0 है, तो झूठी वापसी करें

• सही लौटें

• अब मुख्य विधि से निम्न कार्य करें -

• ssz:=s और tsz का आकार:=t का आकार

• कैरेक्टर टाइप की और ऐरे टाइप वैल्यू का मैप एम बनाएं

• मेरे लिए 0 से ssz की सीमा में

  • m[s[i]]

    . में i डालें

• पूर्व:=-1 और सेवानिवृत्त:=1

• मेरे लिए 0 से tsz की सीमा में

  • अगर t[i] m में मौजूद नहीं है, तो वापसी -1

  • वी:=एम[टी[i]]

  • मैं सेट करें:=v में तत्व की अनुक्रमणिका, जो पूर्व से अधिक है

  • अगर मैं सूची का अंत नहीं हूं

    • रिट को 1 और पूर्व बढ़ाएँ:=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