字符串中的查找与替换

标签: 数组 字符串 排序

难度: Medium

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

Submission

运行时间: 26 ms

内存: 16.1 MB

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        new_indices = []
        shift = 0
        info=sorted(zip(indices, sources, targets))
        for i, src, tar in info:
            new_indices.append(i+shift)
            if s[i:i+len(src)]==src:
                shift += len(tar) - len(src)
        s = list(s)
        for i, (_, src, tar) in zip(new_indices, info):
            src, tar = list(src), list(tar)
            if s[i:i+len(src)]==src:
                s[i:i+len(src)]=tar
        return ''.join(s)

Explain

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

时间复杂度: O(n + klogk)

空间复杂度: O(n + k)

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        new_indices = []
        shift = 0
        # 将替换操作打包成元组并按下标排序
        info = sorted(zip(indices, sources, targets))
        for i, src, tar in info:
            new_indices.append(i + shift)
            # 检查原字符串中是否出现了要替换的子字符串
            if s[i:i+len(src)] == src:
                # 计算替换后的下标偏移量
                shift += len(tar) - len(src)
        # 将原字符串转换为列表
        s = list(s)
        for i, (_, src, tar) in zip(new_indices, info):
            src, tar = list(src), list(tar)
            # 根据新下标进行实际的替换操作
            if s[i:i+len(src)] == src:
                s[i:i+len(src)] = tar
        # 将替换后的字符列表拼接成字符串并返回
        return ''.join(s)

Explore

算法首先对所有替换操作按照原始下标进行排序，这确保了替换从字符串的开始到结束依次进行，避免了后续替换操作受到前面替换影响的下标错位。接着，算法通过维护一个偏移量`shift`来记录因替换导致的下标变化。当替换发生时，如果新字符串长度与原字符串长度不同，则更新`shift`，以反映在该点之后所有替换操作的起始下标的变化。这样，即便替换会改变字符串长度，每次替换也会根据当前`shift`值调整其实际替换位置，从而保证不会相互影响。

偏移量`shift`的计算基于每次替换操作前后字符串长度的变化。在遍历排序后的替换操作时，算法检查每个替换位置的原字符串是否匹配，如果匹配，则替换操作会导致字符串长度变化。具体地，`shift`更新为`shift += len(tar) - len(src)`。这里，`len(tar) - len(src)`表示由于替换产生的长度变化（可以是正的、负的或零）。这个累计的偏移量会应用到后续替换操作的下标计算中，确保每个替换都考虑到了前面替换操作引起的下标变化。

在Python中，字符串是不可变的，这意味着不能直接改变字符串中的单个字符。因此，直接在字符串上进行替换会非常低效，因为每次替换都可能需要创建一个新的字符串。将字符串转换为列表可以使字符成为可变的，从而允许在列表中直接修改字符。这样，替换操作可以直接在列表上进行，完成所有替换后，只需要一次操作就可以将列表转换回字符串，这样可以显著提高效率。

通过排序替换操作，算法确保了按照字符串的自然顺序（从左到右）进行替换，这避免了替换顺序错误引起的潜在问题（比如后面的替换影响前面的替换结果）。此外，排序也使得可以连续地计算偏移量，而不需要在每次替换时重新计算影响到的所有后续替换。这种方法提高了算法的效率，因为每个替换操作只需要基于当前的偏移量进行调整，而无需关心全局的所有替换细节。总体上，这种策略既保证了替换的正确性，也优化了执行速度。