ধরুন আমাদের একটি স্ট্রিং S আছে, আমরা কিছু প্রতিস্থাপন ক্রিয়া সম্পাদন করব যা অক্ষরের গ্রুপগুলিকে নতুন দিয়ে প্রতিস্থাপন করবে। প্রতিটি প্রতিস্থাপন অপারেশনে 3টি পরামিতি রয়েছে - একটি শুরু সূচক i, একটি উত্স শব্দ x এবং একটি লক্ষ্য শব্দ y। এখন নিয়ম হল যদি x আসল স্ট্রিং S-এ i অবস্থান থেকে শুরু হয়, তাহলে আমরা x-এর সেই সংঘটনটিকে y দিয়ে প্রতিস্থাপন করব। অন্যথায়, আমরা কিছুই করি না।
সুতরাং একটি উদাহরণ হিসাবে, বিবেচনা করুন, যদি আমাদের কাছে S ="abcd" থাকে এবং আমাদের কিছু প্রতিস্থাপন অপারেশন থাকে i =2, x ="cd", y ="ffff", তাহলে কারণ "cd" মূল স্ট্রিং এর অবস্থান 2 থেকে শুরু হয় S, আমাদের এটিকে "ffff" দিয়ে প্রতিস্থাপন করতে হবে।
আসুন আমরা S ="abcd" এর আরেকটি উদাহরণ দেখি, যদি আমাদের প্রতিস্থাপন অপারেশন i =0, x ="ab", y ="eee", পাশাপাশি আরেকটি প্রতিস্থাপন অপারেশন i =2, x ="ec" উভয়ই থাকে। , y ="ffff", এই দ্বিতীয় অপারেশনটি কিছুই করে না কারণ আসল স্ট্রিং S[2] ='c', যা x[0] ='e'-এর সাথে মেলে না।
তাই যদি আমাদের একটি স্ট্রিং থাকে S =“abcd”, indices =[0,2] এবং Sources =[“a”, “cd”], এবং targets =[“eee”, “ffff”], তাহলে আউটপুট হবে "eeebffff"। এর কারণ হল "a" S-তে 0 পজিশন থেকে শুরু হয়, তাই এটি "eee" দ্বারা প্রতিস্থাপিত হয়। এখন "cd" শুরু হয় S-তে সূচী 2 থেকে, তাই এটি "ffff" দ্বারা প্রতিস্থাপিত হয়।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- জোড়ার একটি অ্যারে সংজ্ঞায়িত করুন, যাকে বলা হয় সাজানো, n :=সূচক অ্যারের আকার
- আমি 0 থেকে n – 1
- পরিসরে
- সর্টে একটি জোড়া (সূচিপত্র[i], i) সন্নিবেশ করান।
- বিপরীত ক্রমে সাজানো সাজান
- 0 থেকে n – 1
- পরিসরে j এর জন্য
- i :=সাজানো জোড়ার প্রথম মান[j]
- src :=সূত্র[বাছাই করা জোড়ার দ্বিতীয় মান[j]]
- টার্গেট :=টার্গেট[সর্ট করা জোড়ার দ্বিতীয় মান[j]]
- যদি সূচক i থেকে উৎসের আকারে S-এর সাবস্ট্রিং - 1 উৎসের সমান হয়, তাহলে
- S :=(সূচী 0 থেকে i পর্যন্ত S-এর সাবস্ট্রিং) সংযুক্ত লক্ষ্য, সংযোজন (i থেকে উৎসের আকার পর্যন্ত S-এর সাবস্ট্রিং - 1)
- রিটার্ন 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