Medium

题目描述

给你一个下标从 0 开始的字符串 s，你必须对其执行 k 个替换操作。替换操作由三个长度均为 k 的下标从 0 开始的并行数组给出：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 <= indexes[i] < s.length
  • 1 <= sources[i].length, targets[i].length <= 50
  • s 仅由小写英文字母组成
  • sources[i] 和 targets[i] 仅由小写英文字母组成

解题思路

这道题的核心思路是先处理所有的替换操作，然后重新构建字符串。

由于所有替换操作需要同时进行，不能相互影响索引，我们需要：

  1. 验证替换的有效性：对每个替换操作，检查在指定位置是否真的存在目标子字符串
  2. 按位置排序：为了便于处理，我们需要按照索引位置对替换操作进行排序
  3. 重新构建字符串：从左到右遍历原字符串，对于需要替换的位置使用新字符串，否则保持原字符

具体实现步骤：

  • 创建一个索引到替换操作的映射，同时验证每个位置的子字符串是否匹配
  • 按照索引位置排序所有有效的替换操作
  • 从头开始构建新字符串，遇到替换位置时跳过原子字符串的长度，使用替换后的字符串

这种方法的时间复杂度主要来自排序和字符串构建过程，空间复杂度取决于存储替换信息和结果字符串。

代码实现

class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        vector<pair<int, int>> validOps;
        
        // 验证每个替换操作并收集有效的操作
        for (int i = 0; i < indices.size(); i++) {
            int idx = indices[i];
            if (idx + sources[i].length() <= s.length() && 
                s.substr(idx, sources[i].length()) == sources[i]) {
                validOps.push_back({idx, i});
            }
        }
        
        // 按索引位置排序
        sort(validOps.begin(), validOps.end());
        
        string result = "";
        int i = 0, opIdx = 0;
        
        while (i < s.length()) {
            if (opIdx < validOps.size() && i == validOps[opIdx].first) {
                // 执行替换操作
                int origOpIdx = validOps[opIdx].second;
                result += targets[origOpIdx];
                i += sources[origOpIdx].length();
                opIdx++;
            } else {
                // 保持原字符
                result += s[i];
                i++;
            }
        }
        
        return result;
    }
};

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        valid_ops = []
        
        # 验证每个替换操作并收集有效的操作
        for i in range(len(indices)):
            idx = indices[i]
            if idx + len(sources[i]) <= len(s) and s[idx:idx+len(sources[i])] == sources[i]:
                valid_ops.append((idx, i))
        
        # 按索引位置排序
        valid_ops.sort()
        
        result = []
        i = 0
        op_idx = 0
        
        while i < len(s):
            if op_idx < len(valid_ops) and i == valid_ops[op_idx][0]:
                # 执行替换操作
                orig_op_idx = valid_ops[op_idx][1]
                result.append(targets[orig_op_idx])
                i += len(sources[orig_op_idx])
                op_idx += 1
            else:
                # 保持原字符
                result.append(s[i])
                i += 1
        
        return ''.join(result)

public class Solution {
    public string FindReplaceString(string s, int[] indices, string[] sources, string[] targets) {
        var validOps = new List<(int index, int opIndex)>();
        
        // 验证每个替换操作并收集有效的操作
        for (int i = 0; i < indices.Length; i++) {
            int idx = indices[i];
            if (idx + sources[i].Length <= s.Length && 
                s.Substring(idx, sources[i].Length) == sources[i]) {
                validOps.Add((idx, i));
            }
        }
        
        // 按索引位置排序
        validOps.Sort((a, b) => a.index.CompareTo(b.index));
        
        var result = new StringBuilder();
        int pos = 0, opIdx = 0;
        
        while (pos < s.Length) {
            if (opIdx < validOps.Count && pos == validOps[opIdx].index) {
                // 执行替换操作
                int origOpIdx = validOps[opIdx].opIndex;
                result.Append(targets[origOpIdx]);
                pos += sources[origOpIdx].Length;
                opIdx++;
            } else {
                // 保持原字符
                result.Append(s[pos]);
                pos++;
            }
        }
        
        return result.ToString();
    }
}

var findReplaceString = function(s, indices, sources, targets) {
    const operations = [];
    
    for (let i = 0; i < indices.length; i++) {
        const index = indices[i];
        const source = sources[i];
        const target = targets[i];
        
        if (s.substring(index, index + source.length) === source) {
            operations.push({
                index: index,
                length: source.length,
                replacement: target
            });
        }
    }
    
    operations.sort((a, b) => b.index - a.index);
    
    let result = s;
    for (const op of operations) {
        result = result.substring(0, op.index) + op.replacement + result.substring(op.index + op.length);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度值
时间复杂度O(k log k + n + m)
空间复杂度O(k + m)

其中：

  • n 为原字符串 s 的长度
  • k 为替换操作的数量
  • m 为结果字符串的长度
  • 时间复杂度中的 k log k 来自排序，n 来自遍历原字符串，m 来自构建结果字符串
  • 空间复杂度中的 k 来自存储有效替换操作，m 来自结果字符串