Description#
You are given a 0-indexed string s
that you must perform k
replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices
, sources
, and targets
, all of length k
.
To complete the ith
replacement operation:
- Check if the substring
sources[i]
occurs at index indices[i]
in the original string s
. - If it does not occur, do nothing.
- Otherwise if it does occur, replace that substring with
targets[i]
.
For example, if s = "abcd"
, indices[i] = 0
, sources[i] = "ab"
, and targets[i] = "eee"
, then the result of this replacement will be "eeecd"
.
All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.
- For example, a testcase with
s = "abc"
, indices = [0, 1]
, and sources = ["ab","bc"]
will not be generated because the "ab"
and "bc"
replacements overlap.
Return the resulting string after performing all replacement operations on s
.
A substring is a contiguous sequence of characters in a string.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/0833.Find%20And%20Replace%20in%20String/images/833-ex1.png)
Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"
Explanation:
"a" occurs at index 0 in s, so we replace it with "eee".
"cd" occurs at index 2 in s, so we replace it with "ffff".
Example 2:
![](https://spcdn.pages.dev/leetcode/problems/0833.Find%20And%20Replace%20in%20String/images/833-ex2-1.png)
Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" occurs at index 0 in s, so we replace it with "eee".
"ec" does not occur at index 2 in s, so we do nothing.
Constraints:
1 <= s.length <= 1000
k == indices.length == sources.length == targets.length
1 <= k <= 100
0 <= indexes[i] < s.length
1 <= sources[i].length, targets[i].length <= 50
s
consists of only lowercase English letters.sources[i]
and targets[i]
consist of only lowercase English letters.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def findReplaceString(
self, s: str, indices: List[int], sources: List[str], targets: List[str]
) -> str:
n = len(s)
d = [-1] * n
for k, (i, src) in enumerate(zip(indices, sources)):
if s.startswith(src, i):
d[i] = k
ans = []
i = 0
while i < n:
if ~d[i]:
ans.append(targets[d[i]])
i += len(sources[d[i]])
else:
ans.append(s[i])
i += 1
return "".join(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
int n = s.length();
var d = new int[n];
Arrays.fill(d, -1);
for (int k = 0; k < indices.length; ++k) {
int i = indices[k];
if (s.startsWith(sources[k], i)) {
d[i] = k;
}
}
var ans = new StringBuilder();
for (int i = 0; i < n;) {
if (d[i] >= 0) {
ans.append(targets[d[i]]);
i += sources[d[i]].length();
} else {
ans.append(s.charAt(i++));
}
}
return ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
int n = s.size();
vector<int> d(n, -1);
for (int k = 0; k < indices.size(); ++k) {
int i = indices[k];
if (s.compare(i, sources[k].size(), sources[k]) == 0) {
d[i] = k;
}
}
string ans;
for (int i = 0; i < n;) {
if (~d[i]) {
ans += targets[d[i]];
i += sources[d[i]].size();
} else {
ans += s[i++];
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func findReplaceString(s string, indices []int, sources []string, targets []string) string {
n := len(s)
d := make([]int, n)
for k, i := range indices {
if strings.HasPrefix(s[i:], sources[k]) {
d[i] = k + 1
}
}
ans := &strings.Builder{}
for i := 0; i < n; {
if d[i] > 0 {
ans.WriteString(targets[d[i]-1])
i += len(sources[d[i]-1])
} else {
ans.WriteByte(s[i])
i++
}
}
return ans.String()
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| function findReplaceString(
s: string,
indices: number[],
sources: string[],
targets: string[],
): string {
const n = s.length;
const d: number[] = Array(n).fill(-1);
for (let k = 0; k < indices.length; ++k) {
const [i, src] = [indices[k], sources[k]];
if (s.startsWith(src, i)) {
d[i] = k;
}
}
const ans: string[] = [];
for (let i = 0; i < n; ) {
if (d[i] >= 0) {
ans.push(targets[d[i]]);
i += sources[d[i]].length;
} else {
ans.push(s[i++]);
}
}
return ans.join('');
}
|