字符串中的查找与替换

你会得到一个字符串 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 执行所有替换操作后返回 结果字符串 。

子字符串 是字符串中连续的字符序列。

 

示例 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. 使用Stream和Collectors来处理替换操作。
 * 2. 创建一个字符串数组来保存修改后的字符。
 * 3. 遍历indices数组，如果sources[i]出现在s的indices[i]位置，则用targets[i]替换sources[i]。
 * 4. 使用Stream来构建最终的结果字符串。
 */

import java.util.stream.IntStream;

public class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        String[] result = s.split("");
        IntStream.range(0, indices.length).forEach(i -> {
            int index = indices[i];
            String source = sources[i];
            String target = targets[i];
            if (s.startsWith(source, index)) {
                for (int j = 0; j < source.length(); j++) {
                    result[index + j] = "";
                }
                result[index] = target;
            }
        });
        return String.join("", result);
    }
}

本题解的思路是先对替换操作进行排序，计算替换后字符串的下标偏移量。然后再遍历排序后的替换操作，对原字符串进行实际的替换。具体步骤如下： 1. 将替换操作信息(下标、原字符串、目标字符串)打包成元组，并按照下标进行排序。 2. 遍历排序后的替换操作，计算每次替换后的下标偏移量，并记录在 new_indices 中。 3. 将原字符串转换为列表，方便进行字符替换操作。 4. 再次遍历替换操作，并根据 new_indices 中记录的新下标，对原字符串进行实际的替换。 5. 将替换后的字符列表拼接成字符串并返回结果。

O(n + klogk)

O(n + k)