Problem
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:
0 <= indexes.length = sources.length = targets.length <= 100
0 < indexes[i] < S.length <= 1000
- All characters in given inputs are lowercase letters.
Solution 1
/**
* @param {string} S
* @param {number[]} indexes
* @param {string[]} sources
* @param {string[]} targets
* @return {string}
*/
var findReplaceString = function(S, indexes, sources, targets) {
var len = S.length;
var len2 = indexes.length;
var map = {};
var res = '';
var i = 0;
if (len2 === 0) return S;
for (var k = 0; k < len2; k++) {
map[indexes[k]] = [sources[k], targets[k]];
}
while (i < len) {
if (map[i] && S.substr(i, map[i][0].length) === map[i][0]) {
res += map[i][1];
i += Math.max(map[i][0].length, 1);
} else {
res += S[i];
i += 1;
}
}
return res;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
n
为S.length
。 - Space complexity : O(n).
Solution 2
/**
* @param {string} S
* @param {number[]} indexes
* @param {string[]} sources
* @param {string[]} targets
* @return {string}
*/
var findReplaceString = function(S, indexes, sources, targets) {
var len = indexes.length;
var sorted = [];
var map = {};
var index = 0;
if (len === 0) return S;
for (var i = 0; i < len; i++) {
map[indexes[i]] = i;
sorted.push(indexes[i]);
}
sorted.sort((a, b) => a - b);
for (var j = len - 1; j >= 0; j--) {
index = map[sorted[j]];
if (S.substr(sorted[j], sources[index].length) === sources[index]) {
S = S.substr(0, sorted[j]) + targets[index] + S.substr(sorted[j] + sources[index].length);
}
}
return S;
};
Explain:
给 indexes
排序,然后从后往前依次替换。
Complexity:
- Time complexity : O(n * log(n)).
n
为indexes.length
。 - Space complexity : O(n).