友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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 执行所有替换操作后返回 结果字符串 。
子字符串 是字符串中连续的字符序列。
示例 1：
输入：s = "abcd", indices = [0,2], sources = ["a","cd"], targets = ["eee","ffff"] 输出："eeebffff" 解释： "a" 从 s 中的索引 0 开始，所以它被替换为 "eee"。 "cd" 从 s 中的索引 2 开始，所以它被替换为 "ffff"。
示例 2：
输入：s = "abcd", indices = [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 <= indices[i] < s.length -
1 <= sources[i].length, targets[i].length <= 50 -
s仅由小写英文字母组成 -
sources[i]和targets[i]仅由小写英文字母组成
思路分析
对需要替换的数据做排序，利用区间合并的套路，筛选出合格的替换字符串。然后依次做字符串替换。
| 审题不仔细！题目保证不会重叠，还在瞎处理重叠情况。 |
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/**
* 回头得重写一遍！
*
* @author D瓜哥 · https://www.diguage.com
* @since 2026-07-23 21:52:43
*/
public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
List<Data> data = new ArrayList<>(indices.length);
for (int i = 0; i < indices.length; i++) {
data.add(new Data(indices[i], sources[i], targets[i]));
}
data.sort(Comparator.comparingInt(a -> a.index));
List<Data> filter = new ArrayList<>(indices.length);
for (int i = 0; i < indices.length; i++) {
Data d = data.get(i);
// 找到才处理
if (s.startsWith(d.source, d.index)) {
// 没有则直接添加
if (filter.isEmpty()) {
filter.add(d);
} else {
Data last = filter.getLast();
// 判断和前面一个是否重叠
if (last.index + last.source.length() - 1 < d.index) {
// 不重叠
// 前面一个无效，删除
if (!last.filter) {
filter.removeLast();
}
filter.add(d);
} else {
// TIP: 题目保证不会有重叠的！仔细审题啊！
// 有重叠
// 判断哪个更靠后，则保留哪个
if (last.index + last.source.length() < d.index + d.source.length()) {
filter.removeLast();
d.filter = false;
filter.add(d);
} else {
last.filter = false;
}
}
}
}
}
if (!filter.isEmpty() && !filter.getLast().filter) {
filter.removeLast();
}
if (filter.isEmpty()) {
return s;
}
int index = 0;
StringBuilder sb = new StringBuilder();
for (Data d : filter) {
sb.append(s, index, d.index)
.append(d.target);
index = d.index + d.source.length();
}
if (index < s.length()) {
sb.append(s, index, s.length());
}
return sb.toString();
}
private static class Data {
int index;
String source;
String target;
boolean filter = true;
public Data(int index, String source, String target) {
this.index = index;
this.source = source;
this.target = target;
}
}