※ 引述《fxfxxxfxx (爱丽丝)》之铭言：
: 今天的每日一题
: https://i.imgur.com/k8OAIB9.png
: 连题目是什么都不知道 :)
: 这是要怎么写
好像修好了
不过看起来就只是让这题变不是 premium
1061. Lexicographically Smallest Equivalent String
对所有 i，要让 A[i] == B[i]
标准的 union find，把 parent 设成最小的那个就可以了
总共只会有 26*26 = 676 种可能的 query
甚至比 s1 的最大长度 1000 还少
class Solution {
public:
vector<int> parent = vector<int>(128);
int find(int a) {
if (parent[a] != a)
parent[a] = find(parent[a]);
return parent[a];
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u > v) swap(u, v);
parent[v] = u;
}
string smallestEquivalentString(string s1, string s2, string baseStr) {
for (int i = 0; i < 128; i++)
parent[i] = i;
int n = s1.size();
for (int i = 0; i < n; i++)
merge(s1[i], s2[i]);
for (char& c: baseStr)
c = find(c);
return baseStr;
}
};