문자열 S가 있다고 가정하고 문자 그룹을 새 문자 그룹으로 바꾸는 몇 가지 교체 작업을 수행합니다. 각 교체 작업에는 시작 인덱스 i, 소스 단어 x 및 대상 단어 y의 3가지 매개변수가 있습니다. 이제 규칙은 x가 원래 문자열 S의 위치 i에서 시작하면 x의 해당 항목을 y로 대체한다는 것입니다. 그렇지 않으면 아무것도 하지 않습니다.
예를 들어, S ="abcd"이고 일부 대체 연산 i =2, x ="cd", y ="ffff"가 있는 경우 "cd"가 원래 문자열의 위치 2에서 시작하기 때문에 S, 이것을 "ffff"로 바꿔야 합니다.
교체 작업 i =0, x ="ab", y ="eee"와 다른 교체 작업 i =2, x ="ec"가 모두 있는 경우 S ="abcd"에 대한 다른 예를 살펴보겠습니다. , y ="ffff", 이 두 번째 작업은 원래 문자열 S[2] ='c'에서 x[0] ='e'와 일치하지 않기 때문에 아무 작업도 수행하지 않습니다.
따라서 문자열 S ="abcd", 인덱스 =[0,2] 및 소스 =["a", "cd"] 및 대상 =["eee", "ffff"]가 있는 경우 출력은 다음과 같습니다. "에에프프". 이는 "a"가 S의 위치 0에서 시작하여 "eee"로 대체되기 때문입니다. 이제 "cd"는 S의 인덱스 2에서 시작하므로 "ffff"로 대체됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 정렬된 쌍의 배열 정의, n :=인덱스 배열의 크기
- 0 ~ n – 1 범위의 i에 대해
- 정렬된 쌍(indexes[i], i)을 삽입합니다.
- 역순으로 정렬
- 0 ~ n – 1 범위의 j에 대해
- i :=정렬된 쌍의 첫 번째 값[j]
- src :=sources[정렬된 쌍의 두 번째 값[j]]
- target :=target[정렬된 쌍의 두 번째 값[j]]
- 인덱스 i에서 소스 크기까지 S의 부분 문자열 – 1이 소스와 같으면
- 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