2023-08-15 LeetCode每日一题（字符串中的查找与替换）-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023-08-15 LeetCode每日一题（字符串中的查找与替换）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023-08-15每日一题

一、题目编号

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

二、题目链接

点击跳转到题目位置

三、题目描述

你会得到一个字符串 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 执行所有替换操作后返回结果字符串。

子字符串是字符串中连续的字符序列。文章来源地址https://www.toymoban.com/news/detail-650974.html

四、解题代码

class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        int n = s.size(), m = indices.size();

        vector<int> ops(m);
        iota(ops.begin(), ops.end(), 0);
        sort(ops.begin(), ops.end(), [&](int i, int j) { return indices[i] < indices[j]; });

        string ans;
        int pt = 0;
        for (int i = 0; i < n;) {
            while (pt < m && indices[ops[pt]] < i) {
                ++pt;
            }
            bool succeed = false;
            while (pt < m && indices[ops[pt]] == i) {
                if (s.substr(i, sources[ops[pt]].size()) == sources[ops[pt]]) {
                    succeed = true;
                    break;
                }
                ++pt;
            }
            if (succeed) {
                ans += targets[ops[pt]];
                i += sources[ops[pt]].size();
            }
            else {
                ans += s[i];
                ++i;
            }
        }
        return ans;
    }
};