会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
题目要求模拟多次“宝石变色”法术：有 n 颗宝石，初始颜色由一个长度为 n 的小写字母串给出；接下来依次施加 q 次法术，每次给出两个字母 x 和 y，效果是将当前所有颜色为 x 的宝石变成颜色 y。需要输出所有法术结束后每颗宝石的最终颜色。
如果每次法术都真的去扫描整个长度为 n 的宝石序列，单次最坏需要 O(n) 时间，总复杂度将达到 O(nq)，在 n,q≤4×105 时无法通过。
由于颜色仅由 26 个小写字母构成，我们可以利用映射关系来避免反复扫描原序列：
- 维护一个映射数组
mp，其中 mp[c] 表示初始颜色为 c 的宝石，经过当前所有已施展的法术之后，最终会变成什么颜色。
