Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


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

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

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

  • एक मैप m बनाएं

  • s में प्रत्येक कैरेक्टर c के लिए m[c] := 1 मार्क करें

  • t में प्रत्येक कैरेक्टर c के लिए, यदि m[c] 0 है, तो फाल्स लौटाएं

  • ट्रू लौटाएं

  • अब मुख्य मेथड से, निम्नलिखित करें:

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

  • कैरेक्टर प्रकार की कुंजी और सरणी प्रकार के मान का एक मैप m बनाएं

  • i को 0 से ssz तक रेंज में लिए:

    • i को m[s[i]] में डालें

  • pre := -1 और ret := 1

  • i को 0 से tsz तक रेंज में लिए:

    • यदि t[i] m में मौजूद नहीं है, तो -1 लौटाएं

    • v := m[t[i]]

    • i को v में उस तत्व के इंडेक्स के रूप में सेट करें जो pre से बड़ा है

    • यदि i लिस्ट का अंत नहीं है

      • ret को 1 से बढ़ाएं और pre := v[0]

    • अन्यथा pre := v[i]

  • ret लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

#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

  1. - C/C++ में कैसे जांचें कि स्ट्रिंग इंटीजर है?

    यह जांचने के कई तरीके हैं कि स्ट्रिंग इंटीजर है या नहीं और उनमें से एक तरीका isdigit() का उपयोग करके स्ट्रिंग की जांच करना है। उदाहरण #include <iostream> #include <string.h> using namespace std; int main() { char str[] = 3257fg; for (int i = 0; i < strlen(str); i++) {

  1. - C++ में स्ट्रिंग को int में कैसे पार्स करें?

    आप C++ में string stream का उपयोग करके int को पार्स कर सकते हैं। इस मेथड में आपको कुछ एरर चेकिंग करने की आवश्यकता है। उदाहरण #include<iostream> #include<sstream> using namespace std; int str_to_int(const string &str) {    stringstream ss(str);    int num;  

  1. - C++ में int को string में कैसे कन्वर्ट करें?

    आप C से itoa फ़ंक्शन का उपयोग करके int को string में कन्वर्ट कर सकते हैं। उदाहरण #include<iostream> int main() {    int a = 10;    char *intStr = itoa(a);    string str = string(intStr);    cout << str; } आउटपुट यह आउटपुट देगा: 10 यह पूर्णांक को