1061.Lexicographically Smallest Equivalent String === ###### tags: `Medium`,`String`,`Union Find` [1061. Lexicographically Smallest Equivalent String](https://leetcode.com/problems/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. ### 解答 #### C++ ##### 思路: 1. equivalent information由s1,s2定義, 同一個位置char視為一組可互相替換, 不同位置具有傳遞性, 如s1='ab', s2='bc', 則'abc'可互相替換視為一組 2. 題目需找baseStr的Lexicographically Smallest equivalent string, 代表找在baseStr中每一個char同一組最小的char替換 ##### 做法: 1. 同組找老大(最小的char)用disjoint set ```cpp= unordered_map<char,char> root_; char findRoot(char x) { if(x == root_[x]) return x; char root = findRoot(root_[x]); root_[x] = root; return root; } void connect(char x, char y) { char x_root = findRoot(x); char y_root = findRoot(y); if(x_root > y_root) root_[x_root] = y_root; else if(y_root > x_root) root_[y_root] = x_root; } string smallestEquivalentString(string s1, string s2, string baseStr) { for(int i = 0; i < 26; i++) root_['a'+i] = 'a'+i; for(int i = 0; i < s1.length(); i++) connect(s1[i], s2[i]); string res; for(char c : baseStr) res += findRoot(c); return res; } ``` > [name=XD] [time= Jan 14, 2023] Time: $O(n*26)$ Extra Space: $O(26)$ ```cpp= class Solution { public: int parents[26]; int Find(int x) { if (parents[x] == -1) return x; return parents[x] = Find(parents[x]); } void Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) parents[max(x, y)] = min(x, y); } string smallestEquivalentString(string s1, string s2, string baseStr) { memset(parents, -1, sizeof(parents)); for (int i = 0; i < s1.size(); i++) { Union(s1[i] - 'a', s2[i] - 'a'); } for (int i = 0; i < baseStr.size(); i++) { baseStr[i] = Find(baseStr[i] - 'a') + 'a'; } return baseStr; } }; ``` > [name=Yen-Chi Chen][time=Sat, Jan 14, 2023] #### Python ```python= class Solution: def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str: d = defaultdict(lambda: -1) def find(x): if d[x] == -1: return x d[x] = find(d[x]) return d[x] def union(x, y): x, y = find(x), find(y) if x != y: d[max(x, y)] = min(x, y) for a, b in zip(s1, s2): union(a, b) ans = [] for c in baseStr: ans.append(find(c)) return ''.join(ans) ``` > [name=Yen-Chi Chen][time=Sat, Jan 14, 2023] ```python= class Solution: def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str: uf = {} def find(x): uf.setdefault(x, x) if uf[x] != x: uf[x] = find(uf[x]) return uf[x] def union(x, y): x, y = find(x), find(y) if x > y: uf[x] = y else: uf[y] = x for c1, c2 in zip(s1, s2): union(c1, c2) res = [find(c) for c in baseStr] return "".join(res) ``` > [name=Ron Chen][time=Wed, Jan 18, 2023] ### Reference [disjoint set](https://hackmd.io/@CLKO/rkRVS_o-4?type=view) [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)