AtCoder - C - Many Replacement （字符串）

本文主要是介绍AtCoder - C - Many Replacement （字符串），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题陈述

给你一个长度为 $N$ 的字符串 $S$ ，由小写英文字母组成。

您要对字符串 $S$ 进行 $Q$ 次运算。 $i-th$ 运算 $(1\le i\le Q)$ 由一对字符 $(c_i,d_i)$ 表示，它对应于下面的运算：

用字符 $d_i$ 替换 $S$ 中所有出现的字符 $c_i$ 。
完成所有操作后，打印字符串 $S$ 。

限制因素

$1\le N\le 2\times 10^5$
$S$ 是长度为 $N$ 的字符串，由小写英文字母组成。
$1\le Q\le 2\times 10^5$ $c_i$​ 和 $d_i$ 是小写英文字母 $(1\le i\le Q)$ 。
$N$ 和 $Q$ 是整数。

Input

The input is given from Standard Input in the following format:

N
S
Q
c1  d1 
c2  d2 
⋮
cQ  dQ

Output

Print the string S after all operations are completed.

Sample Input 1

7
atcoder
4
r a
t e
d v
a r

Sample Output 1

recover

---

此题乍一看其实没什么，但是最主要的问题是如果出现了以下的操作：
如果出现了a转化为b，b又要转化为a

• 首先如果直接在询问中遍历字符串，那就肯定会TLE
• 如果记录下来每一个字母应该转化到哪一个字母，在询问之后用 $O(N)$ 来搜，那么就会忽视掉变成b之后的a，因为如果扫一遍的话改一个字母就会直接往后扫。

还有其他操作都非常困难，所以给出了这样一种操作。

定义一个修改字母的数组change[26]，在一开始change[i] = i，即每一个字母都对应自己的映射数字。

在操作过程中，如果出现将字母a修改为字母b，那么就去搜26个字母（即整个数组）是否有已经被修改为a的字母，如果有就将该字母的修改值更新为最新操作的更改值b。

这里由于一开始是将每一个字母初始化为自己，所以更改字母的时候不存在更改到无法更改的字母。

---

代码：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2e5 + 10;int change[30];int main() {int n; cin >> n;string str;cin >> str;int q; cin >> q;for (int i = 0; i < 26; i++)change[i] = i;  //初始化while (q--) {char c, d; cin >> c >> d;for (int i = 0; i < 26; i++) {  //扫26个字母if (change[i] == c - 'a')   //如果字母i = 'a'已经被修改为字母c，且这一步操作要将它修改为dchange[i] = d - 'a';    //那就将该字母改为最后的操作对应的字母}}for (int i = 0; i < n; i++) {   //输出时直接输出被修改的字母cout << (char)(change[str[i] - 'a'] + 'a');}return 0;
}

这篇关于AtCoder - C - Many Replacement （字符串）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---