मान लीजिए हमारे पास एक स्ट्रिंग S है, हम कुछ प्रतिस्थापन ऑपरेशन करेंगे जो अक्षरों के समूहों को नए के साथ बदलते हैं। प्रत्येक प्रतिस्थापन ऑपरेशन में 3 पैरामीटर होते हैं - एक प्रारंभिक इंडेक्स i, एक स्रोत शब्द x और एक लक्ष्य शब्द y। अब नियम यह है कि यदि x मूल स्ट्रिंग S में स्थिति i पर शुरू होता है, तो हम x की उस घटना को y से बदल देंगे। अन्यथा, हम कुछ नहीं करते।
तो एक उदाहरण के रूप में, विचार करें, यदि हमारे पास S = "abcd" है और हमारे पास कुछ प्रतिस्थापन ऑपरेशन i = 2, x = "cd", y = "ffff" है, तो क्योंकि "cd" मूल स्ट्रिंग S में स्थिति 2 पर शुरू होता है, हमें इसे "ffff" से बदलना होगा।
आइए S = "abcd" पर एक और उदाहरण देखें, यदि हमारे पास प्रतिस्थापन ऑपरेशन i = 0, x = "ab", y = "eee" दोनों हैं, साथ ही एक और प्रतिस्थापन ऑपरेशन i = 2, x = "ec", y = "ffff", यह दूसरा ऑपरेशन कुछ नहीं करता क्योंकि मूल स्ट्रिंग में S[2] = 'c', जो x[0] = 'e' से मेल नहीं खाता।
तो यदि हमारे पास एक स्ट्रिंग S = "abcd" है, इंडेक्स = [0,2] और स्रोत = ["a", "cd"], और लक्ष्य = ["eee", "ffff"], तो आउटपुट "eeebffff" होगा। ऐसा इसलिए है क्योंकि "a" S में स्थिति 0 पर शुरू होता है, इसलिए इसे "eee" से बदल दिया जाता है। अब "cd" S में इंडेक्स 2 पर शुरू होता है, इसलिए इसे "ffff" से बदल दिया जाता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- जोड़ियों की एक सरणी परिभाषित करें, जिसे सॉर्टेड कहा जाता है, n := इंडेक्स सरणी का आकार
- i को 0 से n - 1 की रेंज में
- (indexes[i], i) जोड़ी को सॉर्टेड में डालें।
- सॉर्टेड को रिवर्स ऑर्डर में सॉर्ट करें
- j को 0 से n - 1 की रेंज में
- i := जोड़ी सॉर्टेड[j] का पहला मान
- src := sources[जोड़ी सॉर्टेड[j] का दूसरा मान]
- target := targets[जोड़ी सॉर्टेड[j] का दूसरा मान]
- यदि इंडेक्स i से स्रोत के आकार - 1 तक S का सबस्ट्रिंग स्रोत के समान है, तो
- S := (इंडेक्स 0 से i तक S का सबस्ट्रिंग) संयोजित लक्ष्य, संयोजित (i से स्रोत के आकार - 1 तक S का सबस्ट्रिंग)
- S लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string findReplaceString(string S, vector<int>& indexes, vector<string>& sources,
vector<string>& targets) {
vector < pair <int, int> > sorted;
int n = indexes.size();
for(int i = 0; i < n; i++){
sorted.push_back({indexes[i], i});
}
sort(sorted.rbegin(), sorted.rend());
for(int j = 0; j < n; j++){
int i = sorted[j].first;
string source = sources[sorted[j].second];
string target = targets[sorted[j].second];
if(S.substr(i, source.size()) == source){
S = S.substr(0, i) + target + S.substr(i + source.size());
}
}
return S;
}
};
main(){
vector<int> v1 = {0, 2};
vector<string> v2 = {"a", "cd"};
vector<string> v3 = {"eee", "ffff"};
Solution ob;
cout << (ob.findReplaceString("abcd", v1, v2, v3));
}
इनपुट
"abcd" [0, 2] ["a", "cd"] ["eee", "ffff"]
आउटपुट
eeebffff
