Question

833. 字符串中的查找与替换

English Version

题目描述

你会得到一个字符串 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] 仅由小写英文字母组成

解法

方法一：模拟

我们遍历每个替换操作，对于当前第 $k$ 个替换操作 $(i, src)$，如果 $s[i..i+|src|-1]$ 与 $src$ 相等，此时我们记录下标 $i$ 处需要替换的是 $targets$ 的第 $k$ 个字符串，否则不需要替换。

接下来，我们只需要遍历原字符串 $s$，根据记录的信息进行替换即可。

时间复杂度 $O(L)$，空间复杂度 $O(n)$。其中 $L$ 是所有字符串的长度之和，而 $n$ 是字符串 $s$ 的长度。

class Solution:
  def findReplaceString(
    self, s: str, indices: List[int], sources: List[str], targets: List[str]
  ) -> str:
    n = len(s)
    d = [-1] * n
    for k, (i, src) in enumerate(zip(indices, sources)):
      if s.startswith(src, i):
        d[i] = k
    ans = []
    i = 0
    while i < n:
      if ~d[i]:
        ans.append(targets[d[i]])
        i += len(sources[d[i]])
      else:
        ans.append(s[i])
        i += 1
    return "".join(ans)

class Solution {
  public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
    int n = s.length();
    var d = new int[n];
    Arrays.fill(d, -1);
    for (int k = 0; k < indices.length; ++k) {
      int i = indices[k];
      if (s.startsWith(sources[k], i)) {
        d[i] = k;
      }
    }
    var ans = new StringBuilder();
    for (int i = 0; i < n;) {
      if (d[i] >= 0) {
        ans.append(targets[d[i]]);
        i += sources[d[i]].length();
      } else {
        ans.append(s.charAt(i++));
      }
    }
    return ans.toString();
  }
}

class Solution {
public:
  string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
    int n = s.size();
    vector<int> d(n, -1);
    for (int k = 0; k < indices.size(); ++k) {
      int i = indices[k];
      if (s.compare(i, sources[k].size(), sources[k]) == 0) {
        d[i] = k;
      }
    }
    string ans;
    for (int i = 0; i < n;) {
      if (~d[i]) {
        ans += targets[d[i]];
        i += sources[d[i]].size();
      } else {
        ans += s[i++];
      }
    }
    return ans;
  }
};

func findReplaceString(s string, indices []int, sources []string, targets []string) string {
  n := len(s)
  d := make([]int, n)
  for k, i := range indices {
    if strings.HasPrefix(s[i:], sources[k]) {
      d[i] = k + 1
    }
  }
  ans := &strings.Builder{}
  for i := 0; i < n; {
    if d[i] > 0 {
      ans.WriteString(targets[d[i]-1])
      i += len(sources[d[i]-1])
    } else {
      ans.WriteByte(s[i])
      i++
    }
  }
  return ans.String()
}

function findReplaceString(
  s: string,
  indices: number[],
  sources: string[],
  targets: string[],
): string {
  const n = s.length;
  const d: number[] = Array(n).fill(-1);
  for (let k = 0; k < indices.length; ++k) {
    const [i, src] = [indices[k], sources[k]];
    if (s.startsWith(src, i)) {
      d[i] = k;
    }
  }
  const ans: string[] = [];
  for (let i = 0; i < n; ) {
    if (d[i] >= 0) {
      ans.push(targets[d[i]]);
      i += sources[d[i]].length;
    } else {
      ans.push(s[i++]);
    }
  }
  return ans.join('');
}