【LetMeFly】833.字符串中的查找与替换

力扣题目链接：https://leetcode.cn/problems/find-and-replace-in-string/

你会得到一个字符串 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：

leetcode.com/uploads/2021/06/12/833-ex1.png" />

输入：s = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
输出："eeebffff"
解释：
"a" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
"cd" 从 s 中的索引 2 开始，所以它被替换为 "ffff"。

示例 2：leetcode.com/uploads/2021/06/12/833-ex2-1.png" />

输入：s = "abcd", indexes = [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 <= indexes[i] < s.length
1 <= sources[i].length, targets[i].length <= 50
s 仅由小写英文字母组成
sources[i] 和 targets[i] 仅由小写英文字母组成

方法一：模拟

首先将“替换信息”indices、sources、targets打包起来，按照indices从小到大排序，记为v。

写一个函数equal(s, toCmp, start)用来判断s从start处开始是否与toCmp匹配。

这样，我们只需要用下标 $i$ 遍历s：

若 $i$ 等于 $v$ 中待处理的 $in d i ces$ ，看字符串 $s$ 从 $i$ 处开始是否与 $v$ 中待处理的 $so u rces$ 匹配：
- 若匹配：进行替换（答案加上对应的 $t a r g e t s$ ， $i$ 加上被替换掉的字符串的长度减1）
- 否则：不进行替换（答案加上 $s [i]$ ）
否则：不进行替换（答案加上 $s [i]$ ）
时间复杂度 $n\log n)$ ，其中 $C$ 是 $so u rces$ 和 $t a r g e t s$ 中字母个数之和， $n = l e n (so u rces)$ 。
空间复杂度 $\log n)$

AC代码

C++

class Solution {
private:
    bool equal(string& s, string& toCmp, int start) {  // 返回s从下标start开始，是否与toCmp匹配
        if (start + toCmp.size() > s.size()) {
            return false;
        }
        for (int i = 0; i < toCmp.size(); i++) {
            if (s[start + i] != toCmp[i]) {
                return false;
            }
        }
        return true;
    }

public:
    string findReplaceString(string& s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        vector<tuple<int, string, string>> v;
        for (int i = 0; i < indices.size(); i++) {
            v.push_back({indices[i], sources[i], targets[i]});
        }
        sort(v.begin(), v.end(), [](tuple<int, string, string>& a, tuple<int, string, string>& b) {
            return get<0>(a) < get<0>(b);
        });
        
        string ans;
        int nowV = 0;
        for (int i = 0; i < s.size(); i++) {
            if (nowV < v.size() && get<0>(v[nowV]) == i) {
                if (equal(s, get<1>(v[nowV]), i)) {
                    ans += get<2>(v[nowV]);
                    i += get<1>(v[nowV]).size() - 1;
                }
                else {
                    ans += s[i];
                }
                nowV++;
            }
            else {
                ans += s[i];
            }
        }
        return ans;
    }
};