2023-08-15力扣每日一题

链接：

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

题意：

n组操作，其中第i组：

1. 检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
2. 如果没有出现， 什么也不做 。
3. 如果出现，则用 targets[i] 替换 该子字符串。

所有替换操作必须 同时 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。

解：

由于要对原字符串进行判断所以我们不对字符串进行直接修改（当然好像弄一个偏移量也可以写原地算法嗷）

由于每组操作互不影响，所以我们按原字符串的下标进行排序，然后从头到尾处理就行，方便字符串拼接和字符串匹配

实际代码：

#include<bits/stdc++.h>
using namespace std;
string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets)
{string ans;int n=indices.size();map<int,int>mp;for(int i=0;i<n;i++) mp[indices[i]]=i;auto it=mp.begin();for(int i=0;i<s.size();i++){if(i==it->first){int mao=s.find(sources[it->second],i);if(mao==i){ans.append(targets[it->second]);i+=sources[it->second].size()-1;}it++;}else ans+=s[i];}return s; 
}
int main()
{string s;cin>>s;int n;cin>>n;vector<int> indices;vector<string> sources,targets;while(n--){int t;string a,b;cin>>t>>a>>b;indices.push_back(t);sources.push_back(a);targets.push_back(b);}string ans=findReplaceString(s,indices,sources,targets);cout<<ans<<endl;return 0;
}

限制：

• 1 <= s.length <= 1000
• k == indices.length == sources.length == targets.length
• 1 <= k <= 100
• 0 <= indices[i] < s.length
• 1 <= sources[i].length, targets[i].length <= 50
• s 仅由小写英文字母组成
• sources[i] 和 targets[i] 仅由小写英文字母组成