# 833. Find And Replace in String

To some string `S`, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has `3` parameters: a starting index `i`, a source word `x` and a target word `y`.  The rule is that if `x` starts at position `i` in the original string `S`, then we will replace that occurrence of `x` with `y`.  If not, we do nothing.

For example, if we have `S = "abcd"` and we have some replacement operation `i = 2, x = "cd", y = "ffff"`, then because `"cd"` starts at position `2` in the original string `S`, we will replace it with `"ffff"`.

Using another example on `S = "abcd"`, if we have both the replacement operation `i = 0, x = "ab", y = "eee"`, as well as another replacement operation `i = 2, x = "ec", y = "ffff"`, this second operation does nothing because in the original string `S[2] = 'c'`, which doesn’t match `x[0] = 'e'`.

All these operations occur simultaneously.  It’s guaranteed that there won’t be any overlap in replacement: for example, `S = "abc", indexes = [0, 1], sources = ["ab","bc"]` is not a valid test case.

Example 1:

``````Input: S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
Output: "eeebffff"
Explanation: "a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".
``````

Example 2:

``````Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation: "ab" starts at index 0 in S, so it's replaced by "eee".
"ec" doesn't starts at index 2 in the original S, so we do nothing.
``````

Notes:

1. `0 <= indexes.length = sources.length = targets.length <= 100`
2. `0 < indexes[i] < S.length <= 1000`
3. All characters in given inputs are lowercase letters.

``````class Solution {
public:
string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
vector<pair<int, int>> v;
for (int i = 0; i < indexes.size(); ++i) {
v.push_back({indexes[i], i});
}
sort(v.rbegin(), v.rend());
for (auto a : v) {
int i = a.first;
string s = sources[a.second], t = targets[a.second];
if (S.substr(i, s.size()) == s) {
S = S.substr(0, i) + t + S.substr(i + s.size());
}
}
return S;
}
};
``````

``````class Solution {
public:
string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
map<int, int, greater<int>> m;
for (int i = 0; i < indexes.size(); ++i) {
m[indexes[i]] = i;
}
for (auto a : m) {
int i = a.first;
string s = sources[a.second], t = targets[a.second];
if (S.substr(i, s.size()) == s) {
S = S.substr(0, i) + t + S.substr(i + s.size());
}
}
return S;
}
};
``````

``````class Solution {
public:
string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
string res = "";
unordered_map<int, int> m;
for (int i = 0; i < indexes.size(); ++i) {
if (S.substr(indexes[i], sources[i].size()) == sources[i]) {
m[indexes[i]] = i;
}
}
for (int i = 0; i < S.size();) {
if (m.count(i)) {
res += targets[m[i]];
i += sources[m[i]].size();
} else {
res.push_back(S[i]);
++i;
}
}
return res;
}
};
``````

``````class Solution {
public:
string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
map<int, pair<int, string>, greater<int>> m;
for (int i = 0; i < indexes.size(); ++i) {
if (S.substr(indexes[i], sources[i].size()) == sources[i]) {
m[indexes[i]] = {sources[i].size(), targets[i]};
}
}
for (auto a : m) {
S.replace(a.first, a.second.first, a.second.second);
}
return S;
}
};
``````

https://leetcode.com/problems/find-and-replace-in-string/

https://leetcode.com/problems/find-and-replace-in-string/discuss/134758/Java-O(n)-solution

https://leetcode.com/problems/find-and-replace-in-string/discuss/130577/C%2B%2B-5-lines-6-ms-bucket-sort-O(n)

https://leetcode.com/problems/find-and-replace-in-string/discuss/130587/C%2B%2BJavaPython-Replace-S-from-right-to-left

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation