{"id":1013,"date":"2017-11-28T15:04:19","date_gmt":"2017-11-28T23:04:19","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1013"},"modified":"2018-04-19T08:30:59","modified_gmt":"2018-04-19T15:30:59","slug":"leetcode-737-sentence-similarity-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-737-sentence-similarity-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 737. Sentence Similarity II"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 737. Sentence Similarity II- \u5237\u9898\u627e\u5de5\u4f5c EP118\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/0rZUi3kZGLI?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Given two sentences\u00a0<code>words1, words2<\/code>\u00a0(each represented as an array of strings), and a list of similar word pairs\u00a0<code>pairs<\/code>, determine if two sentences are similar.<\/p>\n<p>For example,\u00a0<code>words1 = [\"great\", \"acting\", \"skills\"]<\/code>\u00a0and\u00a0<code>words2 = [\"fine\", \"drama\", \"talent\"]<\/code>\u00a0are similar, if the similar word pairs are\u00a0<code>pairs = [[\"great\", \"good\"], [\"fine\", \"good\"], [\"acting\",\"drama\"], [\"skills\",\"talent\"]]<\/code>.<\/p>\n<p>Note that the similarity relation\u00a0<b>is<\/b>\u00a0transitive. For example, if &#8220;great&#8221; and &#8220;good&#8221; are similar, and &#8220;fine&#8221; and &#8220;good&#8221; are similar, then &#8220;great&#8221; and &#8220;fine&#8221;\u00a0<b>are similar<\/b>.<\/p>\n<p>Similarity is also symmetric. For example, &#8220;great&#8221; and &#8220;fine&#8221; being similar is the same as &#8220;fine&#8221; and &#8220;great&#8221; being similar.<\/p>\n<p>Also, a word is always similar with itself. For example, the sentences\u00a0<code>words1 = [\"great\"], words2 = [\"great\"], pairs = []<\/code>\u00a0are similar, even though there are no specified similar word pairs.<\/p>\n<p>Finally, sentences can only be similar if they have the same number of words. So a sentence like\u00a0<code>words1 = [\"great\"]<\/code>\u00a0can never be similar to\u00a0<code>words2 = [\"doubleplus\",\"good\"]<\/code>.<\/p>\n<p><b>Note:<\/b><\/p>\n<ul>\n<li>The length of\u00a0<code>words1<\/code>\u00a0and\u00a0<code>words2<\/code>\u00a0will not exceed\u00a0<code>1000<\/code>.<\/li>\n<li>The length of\u00a0<code>pairs<\/code>\u00a0will not exceed\u00a0<code>2000<\/code>.<\/li>\n<li>The length of each\u00a0<code>pairs[i]<\/code>\u00a0will be\u00a0<code>2<\/code>.<\/li>\n<li>The length of each\u00a0<code>words[i]<\/code>\u00a0and\u00a0<code>pairs[i][j]<\/code>\u00a0will be in the range\u00a0<code>[1, 20]<\/code>.<\/li>\n<\/ul>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<p>\u9898\u76ee\u5927\u610f\uff1a<\/p>\n<p>\u7ed9\u4f60\u4e24\u4e2a\u53e5\u5b50\uff08\u7531\u5355\u8bcd\u6570\u7ec4\u8868\u793a\uff09\u548c\u4e00\u4e9b\u8fd1\u4e49\u8bcd\u5bf9\uff0c\u95ee\u4f60\u8fd9\u4e24\u4e2a\u53e5\u5b50\u662f\u5426\u76f8\u4f3c\uff0c\u5373\u6bcf\u7ec4\u76f8\u5bf9\u5e94\u7684\u5355\u8bcd\u90fd\u8981\u76f8\u4f3c\u3002<\/p>\n<p>\u6ce8\u610f\u76f8\u4f3c\u6027\u53ef\u4ee5\u4f20\u9012\uff0c\u6bd4\u5982\u53ea\u7ed9\u4f60&#8221;great&#8221;\u548c&#8221;fine&#8221;\u76f8\u4f3c\u3001&#8221;fine&#8221;\u548c&#8221;good&#8221;\u76f8\u4f3c\uff0c\u80fd\u63a8\u65ad&#8221;great&#8221;\u548c&#8221;good&#8221;\u4e5f\u76f8\u4f3c\u3002<\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>DFS \/ Union Find<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/737-ep118.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1034\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/737-ep118.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/737-ep118.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/737-ep118-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/737-ep118-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><strong>Solution1:<\/strong><\/p>\n<p>Time complexity: O(|Pairs| * |words1|)<\/p>\n<p>Space complexity: O(|Pairs|)<\/p>\n<p>C++ \/ DFS<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 346 ms\r\nclass Solution {\r\npublic:\r\n    bool areSentencesSimilarTwo(vector&lt;string&gt;&amp; words1, vector&lt;string&gt;&amp; words2, vector&lt;pair&lt;string, string&gt;&gt;&amp; pairs) {\r\n        if (words1.size() != words2.size()) return false;\r\n        \r\n        g_.clear();\r\n        \r\n        for (const auto&amp; p : pairs) {\r\n            g_[p.first].insert(p.second);\r\n            g_[p.second].insert(p.first);\r\n        }\r\n        \r\n        unordered_set&lt;string&gt; visited;\r\n        \r\n        for (int i = 0; i &lt; words1.size(); ++i) {\r\n            visited.clear();\r\n            if (!dfs(words1[i], words2[i], visited)) return false;\r\n        }\r\n        \r\n        return true;\r\n    }\r\nprivate:\r\n    bool dfs(const string&amp; src, const string&amp; dst, unordered_set&lt;string&gt;&amp; visited) {\r\n        if (src == dst) return true;\r\n        visited.insert(src);\r\n        for (const auto&amp; next : g_[src]) {\r\n            if (visited.count(next)) continue;\r\n            if (dfs(next, dst, visited)) return true;\r\n        }\r\n        return false;\r\n    }\r\n    unordered_map&lt;string, unordered_set&lt;string&gt;&gt; g_;\r\n};<\/pre>\n<p>Time complexity: O(|Pairs| + |words1|)<\/p>\n<p>Space complexity: O(|Pairs|)<\/p>\n<p>C++ \/ DFS Optimized<\/p>\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime 229 ms\r\nclass Solution {\r\npublic:\r\n    bool areSentencesSimilarTwo(vector&lt;string&gt;&amp; words1, vector&lt;string&gt;&amp; words2, vector&lt;pair&lt;string, string&gt;&gt;&amp; pairs) {\r\n        if (words1.size() != words2.size()) return false;\r\n        \r\n        g_.clear();\r\n        ids_.clear();\r\n        \r\n        for (const auto&amp; p : pairs) {\r\n            g_[p.first].insert(p.second);\r\n            g_[p.second].insert(p.first);\r\n        }        \r\n        \r\n        int id = 0;\r\n        \r\n        for (const auto&amp; p : pairs) {\r\n            if(!ids_.count(p.first)) dfs(p.first, ++id);\r\n            if(!ids_.count(p.second)) dfs(p.second, ++id);\r\n        }\r\n        \r\n        for (int i = 0; i &lt; words1.size(); ++i) {\r\n            if (words1[i] == words2[i]) continue;\r\n            auto it1 = ids_.find(words1[i]);\r\n            auto it2 = ids_.find(words2[i]);\r\n            if (it1 == ids_.end() || it2 == ids_.end()) return false;\r\n            if (it1-&gt;second != it2-&gt;second) return false;\r\n        }\r\n        \r\n        return true;\r\n    }\r\nprivate:\r\n    bool dfs(const string&amp; curr, int id) {\r\n        ids_[curr] = id;        \r\n        for (const auto&amp; next : g_[curr]) {\r\n            if (ids_.count(next)) continue;\r\n            if (dfs(next, id)) return true;\r\n        }\r\n        return false;\r\n    }\r\n    \r\n    unordered_map&lt;string, int&gt; ids_;\r\n    unordered_map&lt;string, unordered_set&lt;string&gt;&gt; g_;\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Solution2:<\/strong><\/p>\n<p>Time complexity: O(|Pairs| + |words1|)<\/p>\n<p>Space complexity: O(|Pairs|)<\/p>\n<p>C++ \/ Union Find<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 219 ms\r\nclass UnionFindSet {\r\npublic:\r\n    bool Union(const string&amp; word1, const string&amp; word2) {\r\n        const string&amp; p1 = Find(word1, true);\r\n        const string&amp; p2 = Find(word2, true);\r\n        if (p1 == p2) return false;        \r\n        parents_[p1] = p2;\r\n        return true;\r\n    }\r\n    \r\n    const string&amp; Find(const string&amp; word, bool create = false) {\r\n        if (!parents_.count(word)) {\r\n            if (!create) return word;\r\n            return parents_[word] = word;\r\n        }\r\n        \r\n        string w = word;\r\n        while (w != parents_[w]) {\r\n            parents_[w] = parents_[parents_[w]];\r\n            w = parents_[w];\r\n        }\r\n        \r\n        return parents_[w];\r\n    }\r\nprivate:\r\n    unordered_map&lt;string, string&gt; parents_;\r\n};\r\n\r\nclass Solution {\r\npublic:\r\n    bool areSentencesSimilarTwo(vector&lt;string&gt;&amp; words1, vector&lt;string&gt;&amp; words2, vector&lt;pair&lt;string, string&gt;&gt;&amp; pairs) {\r\n        if (words1.size() != words2.size()) return false;\r\n        \r\n        UnionFindSet s;\r\n        for (const auto&amp; pair : pairs)\r\n            s.Union(pair.first, pair.second);\r\n        \r\n        for (int i = 0; i &lt; words1.size(); ++i) \r\n            if (s.Find(words1[i]) != s.Find(words2[i])) return false;\r\n        \r\n        return true;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>C++ \/ Union Find, Optimized<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 175 ms (&lt; 98.45%)\r\nclass UnionFindSet {\r\npublic:\r\n    UnionFindSet(int n) {\r\n        parents_ = vector&lt;int&gt;(n + 1, 0);\r\n        ranks_ = vector&lt;int&gt;(n + 1, 0);\r\n        \r\n        for (int i = 0; i &lt; parents_.size(); ++i)\r\n            parents_[i] = i;\r\n    }\r\n    \r\n    bool Union(int u, int v) {\r\n        int pu = Find(u);\r\n        int pv = Find(v);\r\n        if (pu == pv) return false;\r\n        \r\n        if (ranks_[pu] &gt; ranks_[pv]) {\r\n            parents_[pv] = pu;\r\n        } else if (ranks_[pv] &gt; ranks_[pu]) {\r\n            parents_[pu] = pv;\r\n        } else {\r\n            parents_[pu] = pv;\r\n            ++ranks_[pv];\r\n        }\r\n\r\n        return true;\r\n    }\r\n    \r\n    int Find(int id) {        \r\n        if (id != parents_[id])\r\n            parents_[id] = Find(parents_[id]);        \r\n        return parents_[id];\r\n    }\r\n    \r\nprivate:\r\n    vector&lt;int&gt; parents_;\r\n    vector&lt;int&gt; ranks_;\r\n};\r\n\r\nclass Solution {\r\npublic:\r\n    bool areSentencesSimilarTwo(vector&lt;string&gt;&amp; words1, vector&lt;string&gt;&amp; words2, vector&lt;pair&lt;string, string&gt;&gt;&amp; pairs) {\r\n        if (words1.size() != words2.size()) return false;\r\n        \r\n        UnionFindSet s(pairs.size() * 2);\r\n        \r\n        unordered_map&lt;string, int&gt; indies; \/\/ word to index\r\n        \r\n        for (const auto&amp; pair : pairs) {\r\n            int u = getIndex(pair.first, indies, true);\r\n            int v = getIndex(pair.second, indies, true);\r\n            s.Union(u, v);\r\n        }\r\n        \r\n        for (int i = 0; i &lt; words1.size(); ++i) {\r\n            if (words1[i] == words2[i]) continue;\r\n            int u = getIndex(words1[i], indies);\r\n            int v = getIndex(words2[i], indies);\r\n            if (u &lt; 0 || v &lt; 0) return false;\r\n            if (s.Find(u) != s.Find(v)) return false;\r\n        }\r\n        \r\n        return true;\r\n    }\r\nprivate:\r\n    int getIndex(const string&amp; word, unordered_map&lt;string, int&gt;&amp; indies, bool create = false) {\r\n        auto it = indies.find(word);\r\n        if (it == indies.end()) {\r\n            if (!create) return INT_MIN;\r\n            int index = indies.size();\r\n            indies.emplace(word, index);\r\n            return index;\r\n        }\r\n        \r\n        return it-&gt;second;\r\n    }\r\n};<\/pre>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-734-sentence-similarity\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 734. Sentence Similarity<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-684-redundant-connection\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 684. Redundant Connection<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-685-redundant-connection-ii\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 685. Redundant Connection II<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Given two sentences\u00a0words1, words2\u00a0(each represented as an array of strings), and a list of similar word pairs\u00a0pairs, determine if two sentences are similar. For&#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,164],"tags":[169,113],"class_list":["post-1013","post","type-post","status-publish","format-standard","hentry","category-hashtable","category-medium","tag-similar","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1013","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=1013"}],"version-history":[{"count":19,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1013\/revisions"}],"predecessor-version":[{"id":2572,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1013\/revisions\/2572"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1013"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1013"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1013"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}