【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 = ["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
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(C+nlogn),其中 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 ) n=len(sources) n=len(sources)。
-
空间复杂度 O ( C + log n ) O(C + \log n) O(C+logn)文章来源:https://www.toymoban.com/news/detail-652245.html
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文章来源地址https://www.toymoban.com/news/detail-652245.html
到了这里,关于LeetCode 0833. 字符串中的查找与替换的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!