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

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

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

你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出：indices, sources,  targets。

要完成第 i 个替换操作:

1. 检查 子字符串  sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
2. 如果没有出现， 什么也不做 。
3. 如果出现，则用 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", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
输出："eeebffff"
解释：
"a" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
"cd" 从 s 中的索引 2 开始，所以它被替换为 "ffff"。

示例 2：

输入：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$中待处理的$indices$，看字符串$s$从$i$处开始是否与$v$中待处理的$sources$匹配：

  • 若匹配：进行替换（答案加上对应的$targets$，$i$加上被替换掉的字符串的长度减1）
  • 否则：不进行替换（答案加上$s[i]$）

• 否则：不进行替换（答案加上$s[i]$）

• 时间复杂度$O(C + n\log n)$，其中$C$是$sources$和$targets$中字母个数之和，$n=len(sources)$。

• 空间复杂度$O(C + \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;
    }
};

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/132289306