leetcode 833. Find And Replace in String 字符串中的查找与替换

Problem: 833. Find And Replace in String 字符串中的查找与替换

解题过程

首先按照indices的大小排序，这样s变化以后，才能修改后面的索引，每次比较切片以后的子字符串是否和source当中的相同，若相同也没有被替换过，就切片拼接，索引也相应地修改add，切片比较耗时的

Code

class Solution { public: string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) { vector<bool> status(1001, false); int add = 0, k = indices.size(), now, sz, i; string tg, pre, tail; vector<pair<int, int>> tr; for(int i = 0; i < k; i++) { tr.push_back({indices[i], i}); } sort(tr.begin(), tr.end()); for(int j = 0; j < k; j++) { i = tr[j].second; now = indices[i] + add; sz = sources[i].size(); tg = s.substr(now, sz); if(tg == sources[i] && status[indices[i]]==false) { status[indices[i]] = true; pre = s.substr(0, now); tail = s.substr(now + sz); s = pre + targets[i] + tail; add += targets[i].size() - sz; } } return s; } };