題目

給出長度相同的兩個字符串s1 和 s2 ，還有一個字符串 baseStr 。
其中 s1[i] 和 s2[i] 是一組等價字符。
舉個例子，如果 s1 = “abc” 且 s2 = “cde”，那么就有 ‘a’ == ‘c’, ‘b’ == ‘d’, ‘c’ == ‘e’。
等價字符遵循任何等價關系的一般規則：

• 自反性 ：‘a’ == ‘a’
• 對稱性 ：‘a’ == ‘b’ 則必定有 ‘b’ == ‘a’
• 傳遞性 ：‘a’ == ‘b’ 且 ‘b’ == ‘c’ 就表明 ‘a’ == ‘c’

例如， s1 = “abc” 和 s2 = “cde” 的等價信息和之前的例子一樣，那么 baseStr = “eed” , “acd” 或 “aab”，這三個字符串都是等價的，而 “aab” 是 baseStr 的按字典序最小的等價字符串

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

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

提示：

• 1 <= s1.length, s2.length, baseStr <= 1000
• s1.length == s2.length
• 字符串s1, s2, and baseStr 僅由從 ‘a’ 到 ‘z’ 的小寫英文字母組成。

思路

a == b，b == c，c == d，則a與d存在連通性，查找連通分量可以使用并查集。
注意：在合并s1[i]和s2[i]時，兩個字母的祖先字典序排列較小的作為新的公共祖先

解題過程

1、初始化并查集，因為總共只有26個小寫字母，所以并查集長度為26，每個字母的祖先初始化為其本身。
2、關聯s1與s2中的字母。
3、關聯后再次更新并查集，確保每個字母的祖先最小。
4、遍歷baseStr，生成結果。

Python代碼

def search(node, parent):# 查找祖先節點if node == parent[node]:return nodeparent[node] = search(parent[node], parent)return parent[node]def union(node1, node2, parent):# 關聯node1、node2ancestor1 = search(node1, parent)ancestor2 = search(node2, parent)if ancestor1 < ancestor2:parent[ancestor2] = ancestor1else:parent[ancestor1] = ancestor2class Solution:def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:# 初始化并查集，所有字符(字母)的父節點都是本身parent = list(range(26))# 關聯s1和s2中的每個字母n = len(s1)for i in range(n):a = ord(s1[i]) - ord("a")b = ord(s2[i]) - ord("a")union(a, b, parent)# 更新并查集for i in range(26):search(i, parent)# 生成結果ans = ""for c in baseStr:ans += chr(ord("a") + parent[ord(c) - ord("a")])return ans

C代碼

typedef struct {int* parent;
} UnionFind;UnionFind* createUnionFind(int n) {// 初始化并查集UnionFind* uf = malloc(sizeof(UnionFind));uf->parent = malloc(n * sizeof(int));for (int i = 0; i < n; i++) {uf->parent[i] = i;}return uf;
}int find(int x, UnionFind* uf) {// 查找祖先節點if (uf->parent[x] != x) {uf->parent[x] = find(uf->parent[x], uf);}return uf->parent[x];
}void unite(int x, int y, UnionFind* uf) {x = find(x, uf);y = find(y, uf);if (x == y) return;if (x > y) {uf->parent[x] = y;} else {uf->parent[y] = x;}}char* smallestEquivalentString(char* s1, char* s2, char* baseStr) {// 初始化并查集UnionFind* uf = createUnionFind(26);for (int i = 0; s1[i]; i++) {unite(s1[i] - 'a', s2[i] - 'a', uf);}for (int i = 0; baseStr[i]; i++) {baseStr[i] = 'a' + find(baseStr[i] - 'a', uf);}free(uf->parent);free(uf);return baseStr;
}

復雜度

• 時間復雜度：O((n+m)logC)。其中n是s1和s2的長度，m是baseStr的長度，C是字符集大小，本題中為 26。由于并查集使用了路徑壓縮優化，合并和查找的平均時間復雜度為 O(α( C ))，其中 α 是反阿克曼函數，最差時間復雜度為 O(logC)。

• 空間復雜度：O( C )，C 是字符集大小，本題中為 26，并查集所需的空間是 O( C )。