题解 | #字符串操作#

题目链接

题目描述

给定一个长度为 n 的字符串 s 和 m 次操作。每次操作会提供一个区间 [l, r]（1-based）和两个字符 c1、c2。任务是在字符串 s 的指定区间 [l, r] 内，将所有出现的字符 c1 替换为 c2。按顺序执行完所有 m 次操作后，输出最终的字符串。

输入描述:

第一行输入两个整数 n (字符串长度) 和 m (操作次数)。
第二行输入初始字符串 s。
接下来 m 行，每行输入两个整数 l、r 和两个字符 c1、c2。

输出描述:

输出一个字符串，表示执行完所有操作后的最终结果。

示例:

输入:
```
5 3
wxhak
3 3 h x
1 5 x a
1 3 w g
```
输出: gaaak

解题思路

这道题是对基本字符串操作的考察，核心是直接模拟。由于题目给出的数据范围 (n, m <= 1000) 并不大，一个简单直接的暴力解法就足够通过。

读取初始数据: 首先读取字符串的长度 n、操作次数 m 以及初始字符串 s。
循环处理操作: 使用一个外层循环，从 1 到 m，依次处理每一次操作。
执行单次操作: 在每次循环中： a. 读取区间的左右端点 l、r，以及待替换的源字符 c1 和目标字符 c2。 b. 注意坐标转换: 题目的区间是 1-based（从1开始），而程序中字符串/数组的索引是 0-based（从0开始）。因此，我们需要将 l 和 r 转换为 l-1 和 r-1。 c. 使用一个内层循环，遍历从索引 l-1 到 r-1 的所有位置。 d. 在内层循环中，检查当前位置的字符是否等于 c1。如果等于，就将其修改为 c2。
处理可变性:
- 在 C++ 中，std::string 是可变的，可以直接通过 s[i] = c2; 进行修改。
- 在 Java 中，String 对象是不可变的。因此，更高效的做法是先将 String 转换为 StringBuilder 或 char[]，执行所有修改，最后再转换回 String。StringBuilder 是此场景下的理想选择。
- 在 Python 中，str 也是不可变的。标准做法是先将字符串转换为一个字符列表 list(s)，在列表上进行修改，完成所有操作后，再使用 "".join() 将列表重新组合成字符串。
输出结果: 所有 m 次操作都执行完毕后，打印最终修改后的字符串。

这种 O(m * n) 的解法对于本题的约束是完全足够且易于理解的。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    for (int k = 0; k < m; ++k) {
        int l, r;
        char c1, c2;
        cin >> l >> r >> c1 >> c2;
        // 遍历指定区间 (0-based)
        for (int i = l - 1; i < r; ++i) {
            if (s[i] == c1) {
                s[i] = c2;
            }
        }
    }

    cout << s << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String s = sc.next();

        // 使用 StringBuilder 以支持高效修改
        StringBuilder sb = new StringBuilder(s);

        for (int k = 0; k < m; k++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            char c1 = sc.next().charAt(0);
            char c2 = sc.next().charAt(0);

            // 遍历指定区间 (0-based)
            for (int i = l - 1; i < r; i++) {
                if (sb.charAt(i) == c1) {
                    sb.setCharAt(i, c2);
                }
            }
        }

        System.out.println(sb.toString());
    }
}

# 读取 n 和 m
n, m = map(int, input().split())
# 读取字符串 s
s = input()
# 将不可变的 str 转为可变的 list
char_list = list(s)

for _ in range(m):
    # 读取 l, r, c1, c2
    # 注意这里用 input().split() 一次性读取
    line_parts = input().split()
    l = int(line_parts[0])
    r = int(line_parts[1])
    c1 = line_parts[2]
    c2 = line_parts[3]

    # 遍历指定区间 (0-based)
    for i in range(l - 1, r):
        if char_list[i] == c1:
            char_list[i] = c2

# 将 list 重新组合成 str 并输出
print("".join(char_list))

算法及复杂度

算法: 暴力模拟。
时间复杂度: $\mathcal{O}(M \cdot N)$ ，其中 M 是操作次数，N 是字符串长度。外层循环执行 M 次，内层循环最坏情况下遍历长度为 N 的区间。鉴于 N, M <= 1000，总操作次数在 $10^6$ 级别，可以接受。
空间复杂度: $\mathcal{O}(N)$ 。主要空间用于存储字符串。在 C++ 中是原地修改，空间复杂度为 $\mathcal{O}(1)$ 的额外空间。在 Java 和 Python 中，需要一个 $\mathcal{O}(N)$ 的可变副本（StringBuilder 或 list）。因此，总体空间复杂度为 $\mathcal{O}(N)$ 。