{"id":9916,"date":"2023-01-14T12:24:29","date_gmt":"2023-01-14T20:24:29","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9916"},"modified":"2023-01-14T12:26:14","modified_gmt":"2023-01-14T20:26:14","slug":"leetcode-1061-lexicographically-smallest-equivalent-string","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1061-lexicographically-smallest-equivalent-string\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1061.\u00a0Lexicographically Smallest Equivalent String"},"content":{"rendered":"\n<p>You are given two strings of the same length&nbsp;<code>s1<\/code>&nbsp;and&nbsp;<code>s2<\/code>&nbsp;and a string&nbsp;<code>baseStr<\/code>.<\/p>\n\n\n\n<p>We say&nbsp;<code>s1[i]<\/code>&nbsp;and&nbsp;<code>s2[i]<\/code>&nbsp;are equivalent characters.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, if&nbsp;<code>s1 = \"abc\"<\/code>&nbsp;and&nbsp;<code>s2 = \"cde\"<\/code>, then we have&nbsp;<code>'a' == 'c'<\/code>,&nbsp;<code>'b' == 'd'<\/code>, and&nbsp;<code>'c' == 'e'<\/code>.<\/li><\/ul>\n\n\n\n<p>Equivalent characters follow the usual rules of any equivalence relation:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Reflexivity:<\/strong>&nbsp;<code>'a' == 'a'<\/code>.<\/li><li><strong>Symmetry:<\/strong>&nbsp;<code>'a' == 'b'<\/code>&nbsp;implies&nbsp;<code>'b' == 'a'<\/code>.<\/li><li><strong>Transitivity:<\/strong>&nbsp;<code>'a' == 'b'<\/code>&nbsp;and&nbsp;<code>'b' == 'c'<\/code>&nbsp;implies&nbsp;<code>'a' == 'c'<\/code>.<\/li><\/ul>\n\n\n\n<p>For example, given the equivalency information from&nbsp;<code>s1 = \"abc\"<\/code>&nbsp;and&nbsp;<code>s2 = \"cde\"<\/code>,&nbsp;<code>\"acd\"<\/code>&nbsp;and&nbsp;<code>\"aab\"<\/code>&nbsp;are equivalent strings of&nbsp;<code>baseStr = \"eed\"<\/code>, and&nbsp;<code>\"aab\"<\/code>&nbsp;is the lexicographically smallest equivalent string of&nbsp;<code>baseStr<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the lexicographically smallest equivalent string of&nbsp;<\/em><code>baseStr<\/code><em>&nbsp;by using the equivalency information from&nbsp;<\/em><code>s1<\/code><em>&nbsp;and&nbsp;<\/em><code>s2<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s1 = \"parker\", s2 = \"morris\", baseStr = \"parser\"\n<strong>Output:<\/strong> \"makkek\"\n<strong>Explanation:<\/strong> Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].\nThe characters in each group are equivalent and sorted in lexicographical order.\nSo the answer is \"makkek\".\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s1 = \"hello\", s2 = \"world\", baseStr = \"hold\"\n<strong>Output:<\/strong> \"hdld\"\n<strong>Explanation: <\/strong>Based on the equivalency information in s1 and s2, we can group their characters as [h,w], [d,e,o], [l,r].\nSo only the second letter 'o' in baseStr is changed to 'd', the answer is \"hdld\".\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> s1 = \"leetcode\", s2 = \"programs\", baseStr = \"sourcecode\"\n<strong>Output:<\/strong> \"aauaaaaada\"\n<strong>Explanation:<\/strong> 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\".\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= s1.length, s2.length, baseStr &lt;= 1000<\/code><\/li><li><code>s1.length == s2.length<\/code><\/li><li><code>s1<\/code>,&nbsp;<code>s2<\/code>, and&nbsp;<code>baseStr<\/code>&nbsp;consist of lowercase English letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Union Find<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2023\/01\/1061-s1.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2023\/01\/1061-s1.png\" alt=\"\" class=\"wp-image-9918\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2023\/01\/1061-s1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2023\/01\/1061-s1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2023\/01\/1061-s1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<p>Time complexity: O(n + m)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string smallestEquivalentString(string s1, string s2, string baseStr) {\n    vector<int> p(26);\n    iota(begin(p), end(p), 0);\n    function<int(int)> find = [&](int x) {\n      return p[x] == x ? x : p[x] = find(p[x]);\n    };\n    for (int i = 0; i < s1.length(); ++i) {\n      int r1 = find(s1[i] - 'a');\n      int r2 = find(s2[i] - 'a');\n      if (r2 < r1) swap(r1, r2);\n      p[r2] = r1;\n    }\n    \n    string ans(baseStr);\n    for (int i = 0; i < baseStr.length(); ++i) {\n      ans[i] = find(baseStr[i] - 'a') + 'a';\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given two strings of the same length&nbsp;s1&nbsp;and&nbsp;s2&nbsp;and a string&nbsp;baseStr. We say&nbsp;s1[i]&nbsp;and&nbsp;s2[i]&nbsp;are equivalent characters. For example, if&nbsp;s1 = &#8220;abc&#8221;&nbsp;and&nbsp;s2 = &#8220;cde&#8221;, then we have&nbsp;&#8216;a&#8217;&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[77,177,113],"class_list":["post-9916","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-medium","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9916","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9916"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9916\/revisions"}],"predecessor-version":[{"id":9921,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9916\/revisions\/9921"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9916"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9916"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9916"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}