https://leetcode.com/problems/find-and-replace-in-string/description/
public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
class Solution(object):
def findReplaceString(self, S, indexes, sources, targets):
S = list(S)
for i, x, y in sorted(zip(indexes, sources, targets), reverse = True):
if all(i+k < len(S) and S[i+k] == x[k] for k in xrange(len(x))):
S[i:i+len(x)] = list(y)
return "".join(S)
X.
https://juejin.im/post/5b8098b16fb9a01a1e02056f
https://blog.csdn.net/androidchanhao/article/details/82047678
https://blog.csdn.net/fuxuemingzhu/article/details/81094404
X. Follow up
- If this may happen
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 <= 1000 < indexes[i] < S.length <= 1000- All characters in given inputs are lowercase letters.
- Time Complexity: , where is the length of
S, and we have replacement operations. (Our complexity could be faster with a more accurate implementation, but it isn't necessary.) - Space Complexity: , if we consider
targets[i].length <= 100as a constant bound.
public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
int N = S.length();
int[] match = new int[N];
Arrays.fill(match, -1);
for (int i = 0; i < indexes.length; ++i) {
int ix = indexes[i];
if (S.substring(ix, ix + sources[i].length()).equals(sources[i]))
match[ix] = i;
}
StringBuilder ans = new StringBuilder();
int ix = 0;
while (ix < N) {
if (match[ix] >= 0) {
ans.append(targets[match[ix]]);
ix += sources[match[ix]].length();
} else {
ans.append(S.charAt(ix++));
}
}
return ans.toString();
}
class Solution(object):
def findReplaceString(self, S, indexes, sources, targets):
S = list(S)
for i, x, y in sorted(zip(indexes, sources, targets), reverse = True):
if all(i+k < len(S) and S[i+k] == x[k] for k in xrange(len(x))):
S[i:i+len(x)] = list(y)
return "".join(S)
X.
https://juejin.im/post/5b8098b16fb9a01a1e02056f
https://blog.csdn.net/androidchanhao/article/details/82047678
将
indexes按逆序排序，然后对S从右往左依次查找可替换的单词，如果出现在指定位置，则替换。由于indexes排序后，会变化，因此需要用map结构保存原来的索引。技巧：
- 将indexes按逆序排序；
- 对字符串从右往左处理；
public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> indList = new ArrayList<>();
int n = indexes.length;
for (int i = 0; i < n; i++) {
map.put(indexes[i], i);
indList.add(indexes[i]);
}
Collections.sort(indList);
for (int i = n - 1; i >= 0; i--) {// 从右往左替换
int pos = indList.get(i);
int curInd = map.get(pos);
if (S.indexOf(sources[curInd], pos) == pos) {// 检查sources[curInd]是否出现在指定pos，如果出现，则替换
S = S.substring(0, pos) + targets[curInd] + S.substring(pos + sources[curInd].length());
}
}
return S;
}
https://blog.csdn.net/fuxuemingzhu/article/details/81094404
不可能直接对S进行替换操作的，因为那样直接改变了S的值和长度，影响以后的匹配操作。
This problem is easy. We first build a vector to record the matching index and length to be replaced and the target string.
Then we need to sort the array according to the index, otherwise replacing will cause some trouble.
If we replace the string from left to right, we need append each by each and shall pay attention to what the original string remains. If we do it from right side, then we have no such trouble.
Remember: If you have trouble to do it along one direction, then you may have to think from the other direction. 一个方向有问题， 可能反方向就很好解决。
（1）遍历S字符串的每个位置，在indexes数组中查找该位置是否需要进行替换，如果不需要，则将temp += S中对应字符。
（2）如果S字符串的某个位置在indexes数组中可以查找到，则比较从该起始位置起一段长度的字符串与sources数组中对应的字符串是否相同，如果不相同不进行替换，temp += S中对应字符串。如果相同，用targets数组中对应的字符串替换S中对应字符串，注意将遍历S字符串的下标进行相应的移动。
string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
if (indexes.size() == 0)
return S;
string temp = "";
int flag = 0, j;
for (int i = 0; i < S.length(); ) {
for (j = 0;j < indexes.size(); j++) {
if (i == indexes[j]) {
if (S.substr(i, sources[j].length()) == sources[j]) {
temp += targets[j];
} else {
temp += S.substr(i, sources[j].length());
}
flag = 1;
break;
}
}
if (flag == 0) {
temp += S[i];
i++;
} else {
flag = 0;
i+=sources[j].length();
}
}
return temp;
}
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.