题解 | #转化#_牛客博客

题目链接

题目描述

小美有一个长度为 $n$ ，仅由大小写英文字母组成的字符串 $s$ 。她将对字符串 $s$ 执行 $m$ 次操作，每次操作属于以下两种类型之一：

操作类型 1: 给定两个小写字母 $letter1, letter2$ ( $letter1 \le letter2$ )，将字符串 $s$ 中所有在字母表顺序上属于区间 $[letter1, letter2]$ 的小写字母，转换为对应的大写字母。
操作类型 2: 给定两个大写字母 $letter1, letter2$ ( $letter1 \le letter2$ )，将字符串 $s$ 中所有在字母表顺序上属于区间 $[letter1, letter2]$ 的大写字母，转换为对应的小写字母。

请求出执行完所有操作后得到的最终字符串。

解题思路

本题的核心挑战在于数据规模。字符串长度 $n$ 和操作次数 $m$ 都可能非常大，一个朴素的解法，即对每一次操作都遍历整个长度为 $n$ 的字符串，其时间复杂度为 $\mathcal{O}(n \cdot m)$ ，在 $n, m$ 达到 $2 \cdot 10^5$ 时，计算量过大，必然会导致超时。

因此，我们需要找到一种更高效的策略。注意到所有操作都是针对字符的值进行的，而不是针对其在字符串中的位置。例如，一次操作会改变所有的 'a' 字符，无论它们出现在哪里。这启发我们可以不直接修改原字符串，而是先计算出 “每个初始字符经过所有变换后，最终会变成什么”。

我们可以维护一个字符映射表（transformation map），我们称之为 $mapping$ 。 $mapping[c]$ 用来存储原始字符 $c$ 在经历所有变换后最终的形态。

具体的解题步骤如下：

初始化映射表：创建一个大小为256的数组（足以覆盖所有ASCII字符）作为 $mapping$ 。初始状态下，每个字符都映射到它自身，即 mapping[c] = c。我们主要关心的是 'a'-'z' 和 'A'-'Z'。
模拟操作，更新映射：依次处理 $m$ 个操作。对于每一个操作：
- 例如，一个操作要求将区间 [letter1, letter2] 内的小写字母转为大写。
- 我们需要遍历所有可能的原始字符 c ('a'-'z', 'A'-'Z')，检查它们当前的映射结果 mapping[c] 是否正好在需要被转换的 [letter1, letter2] 区间内。
- 如果 mapping[c] 符合条件，就将其更新为对应的大小写形式。例如，若 mapping[c] 是 'b'，且操作是将 'a'-'c' 转为大写，那么 mapping[c] 就更新为 'B'。
- 这一步是关键，必须遍历所有52个字母的原始状态，来检查它们当前映射后的值是否需要改变，这样才能正确处理连续的转换（如 a -> B -> c）。
最终应用映射：在处理完所有 $m$ 个操作后， $mapping$ 表就包含了从任意一个初始字符到其最终形态的完整转换规则。此时，我们只需遍历一次原始字符串 $s$ ，将其中每个位置的字符 $s[i]$ 替换为其在映射表中的最终形态 mapping[s[i]]。

通过这种方式，我们将主要的计算量从 遍历字符串 转移到了 更新映射表。

代码

c++
java
python

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    // 初始化字符映射表
    vector<char> mapping(256);
    for (int i = 0; i < 256; ++i) {
        mapping[i] = (char)i;
    }

    // 缓存所有需要检查的原始字符
    vector<char> original_chars_to_check;
    for (char c = 'a'; c <= 'z'; ++c) original_chars_to_check.push_back(c);
    for (char c = 'A'; c <= 'Z'; ++c) original_chars_to_check.push_back(c);

    for (int i = 0; i < m; ++i) {
        int op;
        char l1, l2;
        cin >> op >> l1 >> l2;
        
        auto transform_func = (op == 1) ? ::toupper : ::tolower;

        for (char c_to_transform = l1; c_to_transform <= l2; ++c_to_transform) {
            char target_char = transform_func(c_to_transform);
            // 遍历所有可能的原始字符，检查它们的当前映射是否需要被改变
            for (char original_c : original_chars_to_check) {
                if (mapping[original_c] == c_to_transform) {
                    mapping[original_c] = target_char;
                }
            }
        }
    }

    // 一次性应用所有变换
    for (int i = 0; i < n; ++i) {
        s[i] = mapping[s[i]];
    }

    cout << s << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

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

        // 初始化字符映射表
        char[] mapping = new char[256];
        for (int i = 0; i < 256; i++) {
            mapping[i] = (char) i;
        }

        // 缓存所有需要检查的原始字符
        List<Character> originalCharsToCheck = new ArrayList<>();
        for (char c = 'a'; c <= 'z'; c++) originalCharsToCheck.add(c);
        for (char c = 'A'; c <= 'Z'; c++) originalCharsToCheck.add(c);

        for (int i = 0; i < m; i++) {
            int op = sc.nextInt();
            char l1 = sc.next().charAt(0);
            char l2 = sc.next().charAt(0);

            for (char c_to_transform = l1; c_to_transform <= l2; c_to_transform++) {
                char target_char = (op == 1) ? Character.toUpperCase(c_to_transform) : Character.toLowerCase(c_to_transform);
                // 遍历所有可能的原始字符，检查它们的当前映射是否需要被改变
                for (char original_c : originalCharsToCheck) {
                    if (mapping[original_c] == c_to_transform) {
                        mapping[original_c] = target_char;
                    }
                }
            }
        }
        
        // 一次性应用所有变换
        for (int i = 0; i < n; i++) {
            s[i] = mapping[s[i]];
        }

        System.out.println(new String(s));
    }
}

n, m = map(int, input().split())
s = list(input().strip())

lm = [chr(ord('a') + i) for i in range(26)]
um = [chr(ord('A') + i) for i in range(26)]

for _ in range(m):
    op, letter1, letter2 = input().split()
    # op = int(op)
    if op == '1':
        for i in range(ord(letter1) - ord('a'), ord(letter2) - ord('a') + 1):
            lm[i] = lm[i].upper()
            um[i] = um[i].upper()
    else:
        for i in range(ord(letter1) - ord('A'), ord(letter2) - ord('A') + 1):
            lm[i] = lm[i].lower()
            um[i] = um[i].lower()

ans = []

for ch in s:
    if ch.islower():
        ans.append(lm[ord(ch) - ord('a')])
    else:
        ans.append(um[ord(ch) - ord('A')])

print("".join(ans))

算法及复杂度

算法：模拟、字符映射
时间复杂度： $\mathcal{O}(m \cdot |\text{range}| \cdot |\Sigma| + n)$ ，其中 $|\text{range}|$ 是操作区间的平均长度（最大为26）， $|\Sigma|$ 是字母表大小（在此优化实现中为26）。因为 $|\text{range}|$ 和 $|\Sigma|$ 都是常数，所以总的时间复杂度可以简化为 $\mathcal{O}(m+n)$ 。
空间复杂度： $\mathcal{O}(n)$ ，主要由存储输入字符串 $s$ 和结果字符串引起。映射表的空间是 $\mathcal{O}(|\Sigma|)$ ，是常数级别的。