题目
你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出：indices, sources, targets。
要完成第 i 个替换操作:
检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
如果没有出现， 什么也不做 。
如果出现，则用 targets[i] 替换 该子字符串。
例如，如果 s = “abcd” ， indices[i] = 0 , sources[i] = “ab”， targets[i] = “eee” ，那么替换的结果将是 “eeecd” 。
所有替换操作必须 同时 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。
例如，一个 s = “abc” ， indices = [0,1] ， sources = [“ab”，“bc”] 的测试用例将不会生成，因为 “ab” 和 “bc” 替换重叠。
在对 s 执行所有替换操作后返回 结果字符串 。
子字符串 是字符串中连续的字符序列。
示例 1：
输入：s = “abcd”, indices = [0,2], sources = [“a”,“cd”], targets = [“eee”,“ffff”]
输出：“eeebffff”
解释：
“a” 从 s 中的索引 0 开始，所以它被替换为 “eee”。
“cd” 从 s 中的索引 2 开始，所以它被替换为 “ffff”。
示例 2：
输入：s = “abcd”, indices = [0,2], sources = [“ab”,“ec”], targets = [“eee”,“ffff”]
输出：“eeecd”
解释：
“ab” 从 s 中的索引 0 开始，所以它被替换为 “eee”。
“ec” 没有从原始的 S 中的索引 2 开始，所以它没有被替换。
参数范围：
1 <= s.length <= 1000
k == indices.length == sources.length == targets.length
1 <= k <= 100
0 <= indices[i] < s.length
1 <= sources[i].length, targets[i].length <= 50
s 仅由小写英文字母组成
sources[i] 和 targets[i] 仅由小写英文字母组成
分析
将 indices sources targets 按indices的升序排序。可以只对索引排序。
然后依次枚举indices
a，将前面未处理的数据复制到结果串。
b,如果和源串相同则将目标串复制到结果。
c,如果和源串不同，则复制原始串到结果。
变量解释
iNeedDo 未处理的字符起始位置。
代码
class CIndexVector { public: template CIndexVector(vector& data) { for (int i = 0; i < data.size(); i++) { m_indexs.emplace_back(i); } std::sort(m_indexs.begin(), m_indexs.end(), [&data](const int& i1, const int& i2) { return data[i1] < data[i2]; }); } vector m_indexs; }; class Solution { public: string findReplaceString(string s, vector& indices, vector& sources, vector& targets) { CIndexVector indexs(indices); int iNeedDo = 0; string strRet; for (auto& i : indexs.m_indexs) { const int len = indices[i] - iNeedDo; if (len > 0) { strRet += s.substr(iNeedDo, len); iNeedDo += len; } if (s.substr(indices[i], sources[i].length()) == sources[i]) { strRet += targets[i]; iNeedDo += sources[i].length(); } } strRet += s.substr(iNeedDo); return strRet; } };
测试用例
void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector events; int k; string res; { Solution slu; string s = “abcd”; vector indices = { 0, 2 }; vector sources = { “a”, “cd” }, targets = { “eee”, “ffff” }; res = slu.findReplaceString(s, indices, sources, targets); Assert(res, string(“eeebffff”)); } { Solution slu; string s = “vmokgggqzp”; vector indices = { 3, 5, 1 }; vector sources = { “kg”, “ggq”, “mo” }, targets = { “s”, “so”, “bfr” }; res = slu.findReplaceString(s, indices, sources, targets); Assert(res, string(“vbfrssozp”)); }
//CConsole::Out(res);
}
优化版
直接替换，注意 从后向前替换，避免索引发生变化。
s.replace 有多个版本，前两个参数是迭代器的替换左闭右开空间，是整数则是按起始位置和长度替换。
class CIndexVector { public: template<class ELE > CIndexVector(vector<ELE>& data) { for (int i = 0; i < data.size(); i++) { m_indexs.emplace_back(i); } std::sort(m_indexs.begin(), m_indexs.end(), [&data](const int& i1, const int& i2) { return data[i1] < data[i2]; }); } vector<int> m_indexs; }; class Solution { public: string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) { CIndexVector indexs(indices); for (int i = indexs.m_indexs.size()-1; i >= 0 ; i-- ) { const int index = indexs.m_indexs[i]; const int len = sources[index].length(); if (s.substr(indices[index], len) == sources[index]) { s.replace(s.begin()+indices[index], s.begin() + indices[index] + len, targets[index]); } } return s; } };
2022年12月旧版
class Solution { public: string findReplaceString(string s, vector& indices, vector& sources, vector& targets) { string sRet; const int c = indices.size(); vector idxs; for (int i = 0; i < c; i++) { idxs.push_back(i); } std::sort(idxs.begin(), idxs.end(), [&indices](const int& i1,const int& i2){ return indices[i1] < indices[i2]; }); int j = 0; for (int i = 0; i < c; i++) { const int& idx = idxs[i]; while (j < indices[idx]) { sRet += s[j++]; } string tmp = s.substr(indices[idx], sources[idx].length()); if (tmp == sources[idx]) { sRet += targets[idx]; j += tmp.length(); } } while (j < s.length()) { sRet += s[j++]; } return sRet; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
