[LeetCode] 1061. Lexicographically Smallest Equivalent String

You are given two strings of the same length s1 and s2 and a string baseStr.

We say s1[i] and s2[i] are equivalent characters.

• For example, if s1 = "abc" and s2 = "cde", then we have 'a' == 'c', 'b' == 'd', and 'c' == 'e'.

Equivalent characters follow the usual rules of any equivalence relation:

• Reflexivity: 'a' == 'a'.
• Symmetry: 'a' == 'b' implies 'b' == 'a'.
• Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'.

For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr.

Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.

Example 1:

Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".

Example 2:

Input: s1 = "hello", s2 = "world", baseStr = "hold"
Output: "hdld"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [h,w], [d,e,o], [l,r].
So only the second letter 'o' in baseStr is changed to 'd', the answer is "hdld".

Example 3:

Input: s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
Output: "aauaaaaada"
Explanation: We group the equivalent characters in s1 and s2 as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in baseStr except 'u' and 'd' are transformed to 'a', the answer is "aauaaaaada".

Constraints:

• 1 <= s1.length, s2.length, baseStr <= 1000
• s1.length == s2.length
• s1, s2, and baseStr consist of lowercase English letters.

按字典序排列最小的等效字符串。

给出长度相同的两个字符串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 的按字典序排列最小的等价字符串。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lexicographically-smallest-equivalent-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是并查集。

这道题给的是两个字符串 s1 和 s2，两者等长，而且两者对应 index 上的字母是等价的。这里的等价意味着两个字母是可以互相替换的。题目同时又给了一个字符串 baseStr，请按照 s1 和 s2 的等价关系，返回 baseStr 的等价字符串，并需要做到字典序最小。

如果你并查集的题目做多了，看到类似 'a' == 'c', 'b' == 'd', 'c' == 'e' 这种等价关系，和传递性这种关键词，你就能想到用并查集来解决。并查集的特点是可以将同一个连通分量里的点聚在一起，并且声明其中一个点代表这个连通分量。所以这道题我们的思路是用并查集先把 a 里的字符和 b 里的字符连通起来，并用字典序最小的点做这个连通分量的父节点。之后我们遍历 baseStr 的时候，对于其中的每一个字母，我们去看一下这个字母是否能在并查集里的某个连通分量里找到，如果能找到，返回那个连通分量的父节点即可。

时间O(nlogn)

空间O(n)

Java实现

 1 class Solution {
 2     public String smallestEquivalentString(String s1, String s2, String baseStr) {
 3         UnionFind uf = new UnionFind(26);
 4         for (int i = 0; i < s1.length(); i++) {
 5             int a = s1.charAt(i) - 'a';
 6             int b = s2.charAt(i) - 'a';
 7             uf.union(a, b);
 8         }
 9         
10         StringBuilder sb = new StringBuilder();
11         for (int i = 0; i < baseStr.length(); i++) {
12             char c = baseStr.charAt(i);
13             sb.append((char) ('a' + uf.find(c - 'a')));
14         }
15         return sb.toString();
16     }
17 }
18 
19 class UnionFind {
20     int[] parent;
21     
22     public UnionFind(int n) {
23         parent = new int[n];
24         for (int i = 0; i < n; i++) {
25             parent[i] = i;
26         }
27     }
28     
29     public int find(int i) {
30         if (i == parent[i]) {
31             return i;
32         }
33         return parent[i] = find(parent[i]);
34     }
35     
36     public void union(int p, int q) {
37         int pRoot = find(p);
38         int qRoot = find(q);
39         // 谁的字典序小，谁就做父节点
40         if (pRoot < qRoot) {
41             parent[qRoot] = pRoot;
42         } else {
43             parent[pRoot] = qRoot;
44         }
45     }
46 }

LeetCode 题目总结