833.字符串中的查找与替换 (Medium)*
题目描述*
对于某些字符串 S，我们将执行一些替换操作，用新的字母组替换原有的字母组（不一定大小相同）。
每个替换操作具有 3 个参数：起始索引 i，源字 x 和目标字 y。规则是如果 x 从原始字符串 S 中的位置 i 开始，那么我们将用 y 替换出现的 x。如果没有，我们什么都不做。
示例*
如果我们有 S = "abcd" 并且我们有一些替换操作 i = 2，x = "cd"，y = "ffff"，那么因为 "cd" 从原始字符串 S 中的位置 2 开始，我们将用 "ffff" 替换它。
再来看 S = "abcd" 上的另一个例子，如果我们有替换操作 i = 0，x = "ab"，y = "eee"，以及另一个替换操作 i = 2，x = "ec"，y = "ffff"，那么第二个操作将不执行任何操作，因为原始字符串中 S[2] = 'c'，与 x[0] = 'e' 不匹配。
所有这些操作同时发生。保证在替换时不会有任何重叠： S = "abc", indexes = [0, 1], sources = ["ab","bc"] 不是有效的测试用例。
代码*
这里开始想到了 indexes 可能是无序的，但并没有排序，在思考其他的解法，但并没成功。所以还是先用排序解吧。
先把 indexes 排序，然后按照下表从后往前替换，这样替换后的子串位置并不受影响。或者从前往后，要考虑字符串长度的变化。
class Solution {
public:
struct myNode {
int ind;
string s;
string t;
};
static bool compare(myNode &a, myNode &b) {
return a.ind < b.ind;
}
string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
vector<myNode> inputVec;
string res = S;
for(int i = 0; i < indexes.size(); i++) {
inputVec.push_back({indexes[i], sources[i], targets[i]});
}
sort(inputVec.begin(), inputVec.end(), compare);
// 从后往前替换，速度不太行
for(int i = indexes.size() - 1; i >= 0; i--) {
if(res.find(inputVec[i].s, inputVec[i].ind) == inputVec[i].ind) {
// res = res.substr(0, inputVec[i].ind) + inputVec[i].t + res.substr(inputVec[i].ind + inputVec[i].s.length());
//
res.replace(inputVec[i].ind, inputVec[i].s.length(), inputVec[i].t);
}
}
// 从前往后替换，要维护长度变换
// res = "";
// int start = 0;
// for(int i = 0; i < indexes.size(); i++) {
// res += S.substr(start, inputVec[i].ind - start);
// start += inputVec[i].ind - start;
// if(S.find(inputVec[i].s, inputVec[i].ind) == inputVec[i].ind) {
// res += inputVec[i].t;
// start += inputVec[i].s.length();
// }
// }
// res += S.substr(start);
return res;
}
};
最后更新: July 23, 2022