seo批量建站方法,建网站买什么主机,广告词大全,想自己建一个公司网站怎么做【LetMeFly】833.字符串中的查找与替换
力扣题目链接#xff1a;https://leetcode.cn/problems/find-and-replace-in-string/
你会得到一个字符串 s (索引从 0 开始)#xff0c;你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出#xff1a;indices,…【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 [abbc] 的测试用例将不会生成因为 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 1000k indices.length sources.length targets.length1 k 1000 indexes[i] s.length1 sources[i].length, targets[i].length 50s 仅由小写英文字母组成sources[i] 和 targets[i] 仅由小写英文字母组成
方法一模拟
首先将“替换信息”indices、sources、targets打包起来按照indices从小到大排序记为v。
写一个函数equal(s, toCmp, start)用来判断s从start处开始是否与toCmp匹配。
这样我们只需要用下标 i i i遍历s 若 i i i等于 v v v中待处理的 i n d i c e s indices indices看字符串 s s s从 i i i处开始是否与 v v v中待处理的 s o u r c e s sources sources匹配 若匹配进行替换答案加上对应的 t a r g e t s targets targets i i i加上被替换掉的字符串的长度减1否则不进行替换答案加上 s [ i ] s[i] s[i] 否则不进行替换答案加上 s [ i ] s[i] s[i] 时间复杂度 O ( C n log n ) O(C n\log n) O(Cnlogn)其中 C C C是 s o u r c e s sources sources和 t a r g e t s targets targets中字母个数之和 n l e n ( s o u r c e s ) nlen(sources) nlen(sources)。 空间复杂度 O ( C log n ) O(C \log n) O(Clogn)
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, vectorint indices, vectorstring sources, vectorstring targets) {vectortupleint, 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(), [](tupleint, string, string a, tupleint, string, string b) {return get0(a) get0(b);});string ans;int nowV 0;for (int i 0; i s.size(); i) {if (nowV v.size() get0(v[nowV]) i) {if (equal(s, get1(v[nowV]), i)) {ans get2(v[nowV]);i get1(v[nowV]).size() - 1;}else {ans s[i];}nowV;}else {ans s[i];}}return ans;}
};同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/132289306
