2023-08-15每日一題

一、題目編號

833. 字符串中的查找與替換

二、題目鏈接

點擊跳轉到題目位置

三、題目描述

你會得到一個字符串 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 執行所有替換操作后返回 結果字符串 。

子字符串 是字符串中連續的字符序列。

四、解題代碼

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;}
};

五、解題思路