Giả sử chúng ta có một chuỗi S, chúng ta sẽ thực hiện một số thao tác thay thế thay thế các nhóm chữ cái bằng những chữ cái mới. Trong mỗi thao tác thay thế có 3 tham số - chỉ số bắt đầu i, từ nguồn x và từ đích y. Bây giờ quy tắc là nếu x bắt đầu ở vị trí i trong chuỗi ban đầu S, thì chúng ta sẽ thay thế sự xuất hiện đó của x bằng y. nếu không, chúng tôi không làm gì cả.
Vì vậy, như một ví dụ, hãy xem xét, nếu chúng ta có S ="abcd" và chúng ta có một số phép toán thay thế i =2, x ="cd", y ="ffff", thì vì "cd" bắt đầu ở vị trí 2 trong chuỗi ban đầu S, chúng ta phải thay thế điều này bằng "ffff".
Chúng ta hãy xem một ví dụ khác trên S ="abcd", nếu chúng ta có cả phép toán thay thế i =0, x ="ab", y ="eee", cũng như một phép toán thay thế khác i =2, x ="ec" , y ="ffff", thao tác thứ hai này không thực hiện được gì vì trong chuỗi ban đầu S [2] ='c', không khớp với x [0] ='e'.
Vì vậy, nếu chúng ta có một chuỗi S =“abcd”, chỉ số =[0,2] và các nguồn =[“a”, “cd”] và target =[“eee”, “ffff”], thì đầu ra sẽ là "Eeebffff". Điều này là do "a" bắt đầu ở vị trí 0 trong S, vì vậy nó được thay thế bằng "eee". Bây giờ "cd" bắt đầu ở chỉ mục 2 trong S, vì vậy nó được thay thế bằng "ffff".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một mảng các cặp, được gọi là đã sắp xếp, n:=kích thước của mảng chỉ mục
- cho tôi trong phạm vi từ 0 đến n - 1
- chèn một cặp (chỉ mục [i], i) vào đã sắp xếp.
- sắp xếp sắp xếp theo thứ tự ngược lại
- cho j trong phạm vi từ 0 đến n - 1
- i:=giá trị đầu tiên của cặp được sắp xếp [j]
- src:=sources [giá trị thứ hai của cặp được sắp xếp [j]]
- target:=target [giá trị thứ hai của cặp được sắp xếp [j]]
- nếu chuỗi con của S từ chỉ số i đến kích thước của các nguồn - 1 giống với nguồn, thì
- S:=(chuỗi con của S từ chỉ số 0 đến i) nối đích, nối (chuỗi con của S từ i đến kích thước của nguồn - 1)
- trả về S
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
"abcd" [0, 2] ["a", "cd"] ["eee", "ffff"]
Đầu ra
eeebffff