मान लीजिए हमारे पास एक स्ट्रिंग है, हम उस स्ट्रिंग का सबसीक्वेंस कुछ कैरेक्टर्स को हटाकर (संभवतः कोई डिलीशन नहीं) बना सकते हैं। इसलिए अगर दो स्ट्रिंग्स सोर्स और टारगेट हैं, हमें सोर्स के सबसीक्वेंस की न्यूनतम संख्या ढूंढनी है जैसे कि उनका संयोजन टारगेट के बराबर हो। यदि कार्य असंभव है, तो -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