文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給出長度相同的兩個字符串：A 和 B，其中 A[i] 和 B[i] 是一組等價字符。
舉個例子，如果 A = "abc" 且 B = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。

等價字符遵循任何等價關系的一般規則：

自反性：'a' == 'a' 對稱性：'a' == 'b' 則必定有 'b' == 'a' 傳遞性：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c' 例如，A 和 B 的等價信息和之前的例子一樣，那么 S = "eed", "acd" 或 "aab"，這三個字符串都是等價的，而 "aab" 是 S 的按字典序最小的等價字符串

利用 A 和 B 的等價信息，找出并返回 S 的按字典序排列最小的等價字符串。

示例 1： 輸入：A = "parker", B = "morris", S = "parser" 輸出："makkek" 解釋：根據 A 和 B 中的等價信息， 我們可以將這些字符分為 [m,p], [a,o], [k,r,s], [e,i] 共 4 組。 每組中的字符都是等價的，并按字典序排列。所以答案是 "makkek"。示例 2： 輸入：A = "hello", B = "world", S = "hold" 輸出："hdld" 解釋：根據 A 和 B 中的等價信息， 我們可以將這些字符分為 [h,w], [d,e,o], [l,r] 共 3 組。 所以只有 S 中的第二個字符 'o' 變成 'd'，最后答案為 "hdld"。示例 3： 輸入：A = "leetcode", B = "programs", S = "sourcecode" 輸出："aauaaaaada" 解釋：我們可以把 A 和 B 中的等價字符分為 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m] 共 4 組， 因此 S 中除了 'u' 和 'd' 之外的所有字母都轉化成了 'a'，最后答案為 "aauaaaaada"。提示： 字符串 A，B 和 S 僅有從 'a' 到 'z' 的小寫英文字母組成。 字符串 A，B 和 S 的長度在 1 到 1000 之間。 字符串 A 和 B 長度相同。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/lexicographically-smallest-equivalent-string
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

請參考：數據結構–并查集（Disjoint-Set）

• 并查集merge的時候，讓祖先字符更小的作為代表

class dsu {vector<int> f; public:dsu(int n){f.resize(n);for(int i = 0; i < n; ++i)f[i] = i;}void merge(int a, int b){int fa = find(a), fb = find(b);if(fa > fb)//字母小的當代表，關鍵點f[fa] = fb;elsef[fb] = fa;}int find(int a){int origin = a;while(a != f[a])a = f[a];return f[origin] = a;} }; class Solution { public:string smallestEquivalentString(string A, string B, string S) {dsu u(26);for(int i = 0; i < A.size(); ++i)u.merge(A[i]-'a', B[i]-'a');for(int i = 0; i < S.size(); ++i)S[i] = u.find(S[i]-'a')+'a';return S;} };

0 ms 6.7 MB

• 一開始沒想到字符小的作為代表，是用set做了下處理，代碼如下

class dsu { public:vector<int> f;dsu(int n){f.resize(n);for(int i = 0; i < n; ++i)f[i] = i;}void merge(int a, int b){int fa = find(a), fb = find(b);f[fa] = fb;}int find(int a){int origin = a;while(a != f[a])a = f[a];return f[origin] = a;} }; class Solution { public:string smallestEquivalentString(string A, string B, string S) {dsu u(26);for(int i = 0; i < A.size(); ++i)u.merge(A[i]-'a', B[i]-'a');unordered_map<int, set<int>> m;for(int i = 0; i < 26; ++i)m[u.find(i)].insert(i);//分組，set內 begin最小，作為代表for(int i = 0; i < 26; ++i)u.f[i] = *m[u.f[i]].begin();//更新祖先為集團內最小的字符for(int i = 0; i < S.size(); ++i)S[i] = u.find(S[i]-'a')+'a';return S;} };

8 ms 7.4 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode 1061. 按字典序排列最小的等效字符串（并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。