### 题目

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.

### 关键在于下标会变

初始化偏移值修改数组：
[1001, 1001, 1001, 1001]

[2, 1001, 1001, 1001]

[2, 1001, 2, 1001]


#### 代码

class Solution {
public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
StringBuilder sb = new StringBuilder(S);
int[] offsets = new int[S.length()];
Arrays.fill(offsets, 1001);
for (int i = 0; i < indexes.length; i++) {
int offset = 0;
for (int idx = 0; idx < offsets.length; idx++) {
if (offsets[idx] < 1001 && indexes[i] > idx) offset += offsets[idx];
}
StringBuilder newSb = replaceEachString(sb, indexes[i] + offset, sources[i], targets[i]);
if (newSb != null) {
sb = newSb;
int newOffset = targets[i].length() - sources[i].length();
offsets[indexes[i]] = newOffset;
}
}
return new String(sb);
}

// return index of the end of target in original string, return -1 if not valid
private int check(StringBuilder orig, int begin, String target) {
int p = begin;
for (int i = 0; i < target.length(); i++, p++) {
if (p >= orig.length() || orig.charAt(p) != target.charAt(i)) return -1;
}
return p;
}

private StringBuilder replaceEachString(StringBuilder sb, int begin, String source, String target) {
int end = check(sb, begin, source);
if (end >= 0) {
StringBuilder res = new StringBuilder();
res.append(sb.substring(0, begin));
res.append(target);
res.append(sb.substring(end));
return res;
}
return null;
}
}