{"id":7671,"date":"2020-11-14T20:25:44","date_gmt":"2020-11-15T04:25:44","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7671"},"modified":"2020-11-14T20:30:31","modified_gmt":"2020-11-15T04:30:31","slug":"leetcode-1657-determine-if-two-strings-are-close","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1657-determine-if-two-strings-are-close\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1657. Determine if Two Strings Are Close"},"content":{"rendered":"\n<p>Two strings are considered&nbsp;<strong>close<\/strong>&nbsp;if you can attain one from the other using the following operations:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Operation 1: Swap any two&nbsp;<strong>existing<\/strong>&nbsp;characters.<ul><li>For example,&nbsp;<code>abcde&nbsp;-&gt; aecdb<\/code><\/li><\/ul><\/li><li>Operation 2: Transform&nbsp;<strong>every<\/strong>&nbsp;occurrence of one&nbsp;<strong>existing<\/strong>&nbsp;character into another&nbsp;<strong>existing<\/strong>&nbsp;character, and do the same with the other character.<ul><li>For example,&nbsp;<code>aacabb&nbsp;-&gt;&nbsp;bbcbaa<\/code>&nbsp;(all&nbsp;<code>a<\/code>&#8216;s turn into&nbsp;<code>b<\/code>&#8216;s, and all&nbsp;<code>b<\/code>&#8216;s turn into&nbsp;<code>a<\/code>&#8216;s)<\/li><\/ul><\/li><\/ul>\n\n\n\n<p>You can use the operations on either string as many times as necessary.<\/p>\n\n\n\n<p>Given two strings,&nbsp;<code>word1<\/code>&nbsp;and&nbsp;<code>word2<\/code>, return&nbsp;<code>true<\/code><em>&nbsp;if&nbsp;<\/em><code>word1<\/code><em>&nbsp;and&nbsp;<\/em><code>word2<\/code><em>&nbsp;are&nbsp;<strong>close<\/strong>, and&nbsp;<\/em><code>false<\/code><em>&nbsp;otherwise.<\/em><\/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> word1 = \"abc\", word2 = \"bca\"\n<strong>Output:<\/strong> true\n<strong>Explanation:<\/strong> You can attain word2 from word1 in 2 operations.\nApply Operation 1: \"abc\" -&gt; \"acb\"\nApply Operation 1: \"acb\" -&gt; \"bca\"\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> word1 = \"a\", word2 = \"aa\"\n<strong>Output:<\/strong> false\n<strong>Explanation: <\/strong>It is impossible to attain word2 from word1, or vice versa, in any number of operations.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> word1 = \"cabbba\", word2 = \"abbccc\"\n<strong>Output:<\/strong> true\n<strong>Explanation:<\/strong> You can attain word2 from word1 in 3 operations.\nApply Operation 1: \"cabbba\" -&gt; \"caabbb\"\n<code>Apply Operation 2: \"<\/code>caabbb\" -&gt; \"baaccc\"\nApply Operation 2: \"baaccc\" -&gt; \"abbccc\"\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> word1 = \"cabbba\", word2 = \"aabbss\"\n<strong>Output:<\/strong> false\n<strong>Explanation: <\/strong>It is impossible to attain word2 from word1, or vice versa, in any amount of operations.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= word1.length, word2.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>word1<\/code>&nbsp;and&nbsp;<code>word2<\/code>&nbsp;contain&nbsp;only lowercase English letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Hashtable<\/strong><\/h2>\n\n\n\n<p>Two strings are close:<br>1. Have the same length, ccabbb => 6 == aabccc => 6<br>2. Have the same char set, ccabbb => (a, b, c) == aabccc => (a, b, c)<br>3. Have the same sorted char counts ccabbb => (1, 2, 3) == aabccc => (1, 2, 3)<\/p>\n\n\n\n<p>Time complexity: O(n)<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  bool closeStrings(string word1, string word2) {\n    const int l1 = word1.length();\n    const int l2 = word2.length();\n    if (l1 != l2) return false;\n    vector<int> f1(128), f2(128);\n    vector<int> s1(128), s2(128);\n    for (char c: word1) ++f1[c], s1[c] = 1;\n    for (char c: word2) ++f2[c], s2[c] = 1;\n    sort(begin(f1), end(f1));\n    sort(begin(f2), end(f2));\n    return f1 == f2 && s1 == s2;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def closeStrings(self, word1: str, word2: str) -> bool:   \n    c1, c2 = Counter(word1), Counter(word2)\n    return all([len(word1) == len(word2), \n                c1.keys() == c2.keys(),\n                sorted(c1.values()) == sorted(c2.values())])\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Two strings are considered&nbsp;close&nbsp;if you can attain one from the other using the following operations: Operation 1: Swap any two&nbsp;existing&nbsp;characters. For example,&nbsp;abcde&nbsp;-&gt; aecdb Operation 2:&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[288,82,177,4],"class_list":["post-7671","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-count","tag-hashtable","tag-medium","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7671","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=7671"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7671\/revisions"}],"predecessor-version":[{"id":7674,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7671\/revisions\/7674"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7671"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7671"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7671"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}