## 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 = 'c'`, which doesn't match `x = '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.
```

Constraints:

• `0 <= S.length <= 1000`
• `S` consists of only lowercase English letters.
• `0 <= indexes.length <= 100`
• `0 <= indexes[i] < S.length`
• `sources.length == indexes.length`
• `targets.length == indexes.length`
• `1 <= sources[i].length, targets[i].length <= 50`
• `sources[i]` and `targets[i]` consist of only lowercase English letters.

## Rust Solution

``````struct Solution;

type Pair = (usize, usize);

impl Solution {
fn find_replace_string(
mut s: String,
indexes: Vec<i32>,
sources: Vec<String>,
targets: Vec<String>,
) -> String {
let n = indexes.len();
let mut v: Vec<Pair> = vec![];
for i in 0..n {
v.push((indexes[i] as usize, i));
}
v.sort_unstable();
for (i, j) in v.into_iter().rev() {
let source = &sources[j];
let m = source.len();
let target = &targets[j];
if i + m <= s.len() && &s[i..i + m] == source {
s.replace_range(i..i + m, target);
}
}
s
}
}

#[test]
fn test() {
let s = "abcd".to_string();
let indexes = vec![0, 2];
let sources = vec_string!["a", "cd"];
let targets = vec_string!["eee", "ffff"];
let res = "eeebffff".to_string();
assert_eq!(
Solution::find_replace_string(s, indexes, sources, targets),
res
);
let s = "abcd".to_string();
let indexes = vec![0, 2];
let sources = vec_string!["ab", "ec"];
let targets = vec_string!["eee", "ffff"];
let res = "eeecd".to_string();
assert_eq!(
Solution::find_replace_string(s, indexes, sources, targets),
res
);
}
``````

Having problems with this solution? Click here to submit an issue on github.