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

难度: 中等

来源: 每日一题 2023.08.15

---

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

class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {

    }
}

分析与题解

---

• HashMap + 模拟法 + 指针跳动法

  这个题目我在做之前一直在想有没有可以优化的点利用,唯一想到的就是 利用 HashMap进行时间复杂度的降维处理( O(n²) → O(2n)) ,思来想去还就是暴力模拟法了,结果做完发现官方解法也是 HashMap + 模拟法 ...

  在题目的最前面, 我们还是需要做边界处理. 也就是当 indices 替换数组为空时, 我们直接返回 s 即可.

  if (indices.length == 0) {
      return s;
  }
  

  由于 indices, sources, targets 并不是严格意义上的升序数组, 所以我们要利用HashMap进行空间的压缩, 当需要某个下标时, 我们可以直接从 HashMap 中取出对应的数据来.

      Map<Integer, String[]> cache = new HashMap<Integer, String[]>();
      for (int i = 0; i < indices.length; i++) {
          String[] value = {sources[i], targets[i]};
          cache.put(indices[i], value);
      }
  

  接下来, 我们就需要遍历原始字符串 s 了, 主要有以下两种情况需要进行处理.

  • 当 cache.get(i) 不为空时, 也就是说当前找到需要替换的字符, 判断从下标 i 开始是否含有对应的 source. 如果有, 那么就把 target 添加到结果字符串, 并且 下标 i 需要跳动到 source.length -1 + i 位置即可.

  if (cache.get(i) != null) {
      String[] value = cache.get(i);
      String source = value[0];
      String target = value[1];
      String substring = s.substring(i, source.length() + i);
      if (substring.equals(source)) {
          // 指针跳动
          result += target;
          i += source.length() - 1;
          continue;
      }
  }
  
  

  如果没有匹配到, 那么直接把 s[i] 添加到结果中.

  result += s.substring(i, i+1);
  

  最后我们看一下整体的代码.

  class Solution {
      public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
          if (indices.length == 0) {
              return s;
          }
          // 指针跳动法
          Map<Integer, String[]> cache = new HashMap<Integer, String[]>();
          String result = "";
          for (int i = 0; i < indices.length; i++) {
              String[] value = {sources[i], targets[i]};
              cache.put(indices[i], value);
          }
          for(int i = 0; i < s.length(); i++) {
              if (cache.get(i) != null) {
                  String[] value = cache.get(i);
                  String source = value[0];
                  String target = value[1];
                  String substring = s.substring(i, source.length() + i);
                  if (substring.equals(source)) {
                      // 指针跳动
                      result += target;
                      i += source.length() - 1;
                      continue;
                  }
              }
              result += s.substring(i, i+1);
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(2n)
  • 空间复杂度: O(3m), m为indices的长度

  结果如下所示.