※ 引述《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;
}
};