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”, 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] 仅由小写英文字母组成

解法一：一次遍历

 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


func findReplaceString(s string, indices []int, sources []string, targets []string) string {

    buf := make([]string, len(s))
    for j, i := range indices {
        pS := 0
        for k := i; k < len(s) && pS < len(sources[j]); {
            if s[k] != sources[j][pS] {
                break
            }
            k++
            pS++
        }
        if pS == len(sources[j]) {
            buf[i] = targets[j]
            for k := 1; k < len(sources[j]); k++ {
                buf[i+k] = "-"
            }
        }
    }
    stb := strings.Builder{}
    for i, piece := range buf {
        if buf[i] == "" {
            stb.WriteByte(s[i])
        } else if buf[i] != "-" {
            stb.WriteString(piece)
        }
    }
    return stb.String()
}