मान लीजिए हम लोअरकेस अक्षरों की एक लक्ष्य स्ट्रिंग बनाना चाहते हैं।
पहले, हमारे पास n '?' चिह्नों का अनुक्रम होता है (n लक्ष्य स्ट्रिंग की लंबाई है)। हमारे पास लोअरकेस अक्षरों का एक स्टैम्प भी होता है।
प्रत्येक चाल में, हम स्टैम्प को अनुक्रम पर रख सकते हैं, और स्टैम्प में प्रत्येक अक्षर को उस स्टैम्प के संबंधित अक्षर से बदल सकते हैं। आप 10 * n चाल तक बना सकते हैं। उदाहरण के लिए प्रारंभिक अनुक्रम "?????" है, और स्टैम्प "abc" है, तो हम पहली चाल में "abc??", "?abc?", "??abc" जैसी स्ट्रिंग्स बना सकते हैं।
यदि अनुक्रम को स्टैम्प करना संभव है, तो प्रत्येक चाल में बाएं-मोस्ट अक्षर स्टैम्प होने के इंडेक्स की सरणी लौटाएं। यदि यह संभव नहीं है तो एक खाली सरणी लौटाएं। इसलिए जब अनुक्रम "ababc" है, और स्टैम्प "abc" है, तो उत्तर [0, 2] जैसा हो सकता है, क्योंकि हम बना सकते हैं "?????" -> "abc??" -> "ababc"।
यदि इनपुट stamp = "abcd", target = "abcdbcd" है, तो आउटपुट [3,0] होगा।
हल करने के चरण
एक सरणी ret परिभाषित करें
ok := true, n := stamp का आकार, tsz := 0
जब तक ok शून्येतर है: ok := false, x := 0
stamp के आकार से 1 तक घटते हुए sz के लिए: 0 से stamp आकार-sz तक i के लिए
newStamp := लंबाई i के '*' का स्ट्रिंग + stamp का उपस्ट्रिंग i से sz-1 तक + stamp आकार के '*' का स्ट्रिंग
pos := target में newStamp का इंडेक्स
जब तक pos target में मौजूद है: ok := true, x += sz, ret में pos डालें, target को pos से pos+stamp आकार तक '*' से भरें, pos को फिर से खोजें
tsz += x
ret सरणी को उलटें
यदि tsz, target के आकार के बराबर है तो ret लौटाएं, अन्यथा खाली सरणी
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v) {
cout << "[";
for(int i = 0; i < v.size(); i++) { cout << v[i] << ", "; }
cout << "]" << endl;
}
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
vector<int> ret;
bool ok = true;
int n = stamp.size();
int tsz = 0;
while (ok) {
ok = false;
int x = 0;
for (int sz = stamp.size(); sz > 0; sz--) {
for (int i = 0; i <= stamp.size() - sz; i++) {
string newStamp = string(i, '*') + stamp.substr(i, sz) + string(stamp.size() - sz - i, '*');
int pos = target.find(newStamp);
while (pos != string::npos) {
ok = true;
x += sz;
ret.push_back(pos);
fill(target.begin() + pos, target.begin() + pos + stamp.size(), '*');
pos = target.find(newStamp);
}
}
}
tsz += x;
}
reverse(ret.begin(), ret.end());
return tsz == target.size() ? ret : vector<int>();
}
};
int main() {
Solution ob;
print_vector(ob.movesToStamp("abcd", "abcdbcd"));
return 0;
}
इनपुट
"abcd", "abcdbcd"
आउटपुट
[3, 0, ]
