{"id":1006,"date":"2017-11-28T14:17:26","date_gmt":"2017-11-28T22:17:26","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1006"},"modified":"2018-09-04T02:04:16","modified_gmt":"2018-09-04T09:04:16","slug":"leetcode-734-sentence-similarity","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-734-sentence-similarity\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 734. Sentence Similarity"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 734. Sentence Similarity - \u5237\u9898\u627e\u5de5\u4f5c EP117\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/KAX277fYKMM?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, &#8220;great acting skills&#8221; and &#8220;fine drama talent&#8221; are similar, if the similar word pairs are\u00a0<code>pairs = [[\"great\", \"fine\"], [\"acting\",\"drama\"], [\"skills\",\"talent\"]]<\/code>.<\/p>\n<p>Note that the similarity relation is not transitive. For example, if &#8220;great&#8221; and &#8220;fine&#8221; are similar, and &#8220;fine&#8221; and &#8220;good&#8221; are similar, &#8220;great&#8221; and &#8220;good&#8221; are\u00a0<b>not<\/b>\u00a0necessarily similar.<\/p>\n<p>However, similarity is 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\u4e0d\u80fd\u4f20\u9012\uff0c\u6bd4\u5982\u7ed9\u53ea\u4f60&#8221;great&#8221;\u548c&#8221;fine&#8221;\u76f8\u4f3c\u3001&#8221;fine&#8221;\u548c&#8221;good&#8221;\u76f8\u4f3c\uff0c\u8fd9\u79cd\u60c5\u51b5\u4e0b&#8221;great&#8221;\u548c&#8221;good&#8221;\u4e0d\u76f8\u4f3c\u3002<\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>Use hashtable to store mapping from word to its similar words.<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/734-ep117.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1028\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/734-ep117.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/734-ep117.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/734-ep117-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/734-ep117-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<h1><strong>Solution: HashTable<\/strong><\/h1>\n<p>Time complexity: O(|pairs| + |words1|)<\/p>\n<p>Space complexity:\u00a0O(|pairs|)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 9 ms\r\nclass Solution {\r\npublic:\r\n    bool areSentencesSimilar(vector&lt;string&gt;&amp; words1, vector&lt;string&gt;&amp; words2, vector&lt;pair&lt;string, string&gt;&gt; pairs) {\r\n        if (words1.size() != words2.size()) return false;\r\n        \r\n        unordered_map&lt;string, unordered_set&lt;string&gt;&gt; similar_words;\r\n        for (const auto&amp; pair : pairs) {            \r\n            similar_words[pair.first].insert(pair.second);\r\n            similar_words[pair.second].insert(pair.first);\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            if (!similar_words[words1[i]].count(words2[i])) return false;\r\n        }\r\n        \r\n        return true;\r\n    }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 10 ms\r\nclass Solution {\r\n    public boolean areSentencesSimilar(String[] words1, String[] words2, String[][] pairs) {\r\n        if (words1.length != words2.length) return false;\r\n        \r\n        Map&lt;String, Set&lt;String&gt;&gt; similar_words = new HashMap&lt;&gt;();\r\n        \r\n        for (String[] pair : pairs) {\r\n            if (!similar_words.containsKey(pair[0]))\r\n                similar_words.put(pair[0], new HashSet&lt;&gt;());\r\n            if (!similar_words.containsKey(pair[1]))\r\n                similar_words.put(pair[1], new HashSet&lt;&gt;());\r\n            similar_words.get(pair[0]).add(pair[1]);\r\n            similar_words.get(pair[1]).add(pair[0]);\r\n        }\r\n        \r\n        for (int i = 0; i &lt; words1.length; ++i) {\r\n            if (words1[i].equals(words2[i])) continue;\r\n            if (!similar_words.containsKey(words1[i])) return false;\r\n            if (!similar_words.get(words1[i]).contains(words2[i])) return false;\r\n        }\r\n        \r\n        return true;\r\n    }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRuntime: 62 ms\r\n\"\"\"\r\nclass Solution:\r\n    def areSentencesSimilar(self, words1, words2, pairs):\r\n        if len(words1) != len(words2): return False\r\n        \r\n        similar_words = {}\r\n        \r\n        for w1, w2 in pairs:\r\n            if not w1 in similar_words: similar_words[w1] = set()\r\n            if not w2 in similar_words: similar_words[w2] = set()\r\n            similar_words[w1].add(w2)\r\n            similar_words[w2].add(w1)\r\n        \r\n        for w1, w2 in zip(words1, words2):\r\n            if w1 == w2: continue\r\n            if w1 not in similar_words: return False\r\n            if w2 not in similar_words[w1]: return False\r\n        \r\n        return True<\/pre>\n<\/div><\/div>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-737-sentence-similarity-ii\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 737. Sentence Similarity 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":[163,70],"tags":[82,4,168],"class_list":["post-1006","post","type-post","status-publish","format-standard","hentry","category-easy","category-hashtable","tag-hashtable","tag-string","tag-words","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1006","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=1006"}],"version-history":[{"count":14,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1006\/revisions"}],"predecessor-version":[{"id":3853,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1006\/revisions\/3853"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1006"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1006"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1006"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}