{"id":8300,"date":"2021-04-03T11:51:07","date_gmt":"2021-04-03T18:51:07","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8300"},"modified":"2021-04-03T11:52:27","modified_gmt":"2021-04-03T18:52:27","slug":"leetcode-1813-sentence-similarity-iii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1813-sentence-similarity-iii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1813. Sentence Similarity III"},"content":{"rendered":"\n

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. For example, \"Hello World\"<\/code>, \"HELLO\"<\/code>, \"hello world hello world\"<\/code> are all sentences. Words consist of only<\/strong> uppercase and lowercase English letters.<\/p>\n\n\n\n

Two sentences sentence1<\/code> and sentence2<\/code> are similar<\/strong> if it is possible to insert an arbitrary sentence (possibly empty)<\/strong> inside one of these sentences such that the two sentences become equal. For example, sentence1 = \"Hello my name is Jane\"<\/code> and sentence2 = \"Hello Jane\"<\/code> can be made equal by inserting \"my name is\"<\/code> between \"Hello\"<\/code> and \"Jane\"<\/code> in sentence2<\/code>.<\/p>\n\n\n\n

Given two sentences sentence1<\/code> and sentence2<\/code>, return true<\/code> if <\/em>sentence1<\/code> and <\/em>sentence2<\/code> are similar.<\/em> Otherwise, return false<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> sentence1 = \"My name is Haley\", sentence2 = \"My Haley\"\nOutput:<\/strong> true\nExplanation:<\/strong> sentence2 can be turned to sentence1 by inserting \"name is\" between \"My\" and \"Haley\".\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> sentence1 = \"of\", sentence2 = \"A lot of words\"\nOutput:<\/strong> false\nExplanation: <\/strong>No single sentence can be inserted inside one of the sentences to make it equal to the other.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> sentence1 = \"Eating right now\", sentence2 = \"Eating\"\nOutput:<\/strong> true\nExplanation:<\/strong> sentence2 can be turned to sentence1 by inserting \"right now\" at the end of the sentence.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> sentence1 = \"Luky\", sentence2 = \"Lucccky\"\nOutput:<\/strong> false\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= sentence1.length, sentence2.length <= 100<\/code><\/li>
  • sentence1<\/code> and sentence2<\/code> consist of lowercase and uppercase English letters and spaces.<\/li>
  • The words in sentence1<\/code> and sentence2<\/code> are separated by a single space.<\/li><\/ul>\n\n\n\n
    Solution: Dequeue \/ Common Prefix + Suffix<\/strong><\/h2>\n\n\n\n
    Break sequences to words, store them in two deques. Pop the common prefix and suffix. At least one of the deque should be empty.<\/p>\n\n\n\n
    Time complexity: O(m+n)
    Space complexity: O(m+n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool areSentencesSimilar(string s1, string s2) {    \n    auto getWords = [](const string& s) {\n      stringstream ss(s);\n      deque words;\n      while (ss) {\n        words.emplace_back(\"\");\n        ss >> words.back();\n      }\n      return words;\n    };\n    deque w1 = getWords(s1), w2 = getWords(s2);\n    while (w1.size() && w2.size() && w1.front() == w2.front())\n      w1.pop_front(), w2.pop_front();\n    while (w1.size() && w2.size() && w1.back() == w2.back())\n      w1.pop_back(), w2.pop_back();\n    return w1.empty() || w2.empty();\n  }\n};\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua\nclass Solution:\n  def areSentencesSimilar(self, s1: str, s2: str) -> bool:\n    w1 = deque(s1.split())\n    w2 = deque(s2.split())\n    while w1 and w2 and w1[0] == w2[0]:\n      w1.popleft(), w2.popleft()\n    while w1 and w2 and w1[-1] == w2[-1]:\n      w1.pop(), w2.pop()\n    return len(w1) * len(w2) == 0\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    A sentence is a list of words that are separated by a single space with no leading or trailing spaces. For example, “Hello World”, “HELLO”, “hello world hello…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[214,177,4],"class_list":["post-8300","post","type-post","status-publish","format-standard","hentry","category-string","tag-deque","tag-medium","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8300","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=8300"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8300\/revisions"}],"predecessor-version":[{"id":8302,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8300\/revisions\/8302"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8300"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8300"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8300"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}