{"id":6481,"date":"2020-03-14T11:14:40","date_gmt":"2020-03-14T18:14:40","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6481"},"modified":"2020-03-14T15:14:52","modified_gmt":"2020-03-14T22:14:52","slug":"leetcode-87-scramble-string","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-87-scramble-string\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 87. Scramble String"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 87. Scramble String - \u5237\u9898\u627e\u5de5\u4f5c EP314\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/sETxfdHwxc0?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>\n<\/div><\/figure>\n\n\n\n<p>Given a string&nbsp;<em>s1<\/em>, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.<\/p>\n\n\n\n<p>Below is one possible representation of&nbsp;<em>s1<\/em>&nbsp;=&nbsp;<code>\"great\"<\/code>:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">    great\n   \/    \\\n  gr    eat\n \/ \\    \/  \\\ng   r  e   at\n           \/ \\\n          a   t\n<\/pre>\n\n\n\n<p>To scramble the string, we may choose any non-leaf node and swap its two children.<\/p>\n\n\n\n<p>For example, if we choose the node&nbsp;<code>\"gr\"<\/code>&nbsp;and swap its two children, it produces a scrambled string&nbsp;<code>\"rgeat\"<\/code>.<\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">    rgeat\n   \/    \\\n  rg    eat\n \/ \\    \/  \\\nr   g  e   at\n           \/ \\\n          a   t\n<\/pre>\n\n\n\n<p>We say that&nbsp;<code>\"rgeat\"<\/code>&nbsp;is a scrambled string of&nbsp;<code>\"great\"<\/code>.<\/p>\n\n\n\n<p>Similarly, if we continue to swap the children of nodes&nbsp;<code>\"eat\"<\/code>&nbsp;and&nbsp;<code>\"at\"<\/code>, it produces a scrambled string&nbsp;<code>\"rgtae\"<\/code>.<\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">    rgtae\n   \/    \\\n  rg    tae\n \/ \\    \/  \\\nr   g  ta  e\n       \/ \\\n      t   a\n<\/pre>\n\n\n\n<p>We say that&nbsp;<code>\"rgtae\"<\/code>&nbsp;is a scrambled string of&nbsp;<code>\"great\"<\/code>.<\/p>\n\n\n\n<p>Given two strings&nbsp;<em>s1<\/em>&nbsp;and&nbsp;<em>s2<\/em>&nbsp;of the same length, determine if&nbsp;<em>s2<\/em>&nbsp;is a scrambled string of&nbsp;<em>s1<\/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> s1 = \"great\", s2 = \"rgeat\"\n<strong>Output:<\/strong> true\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 = \"abcde\", s2 = \"caebd\"\n<strong>Output:<\/strong> false<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Recursion<\/strong><\/h2>\n\n\n\n<p>isScramble(s1, s2)<br>if s1 == s2: return true<br>if sorted(s1) != sroted(s2): return false<br>We try all possible partitions: <\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>s1[0:l] v.s s2[0:l] &amp;&amp; s1[l:] vs s2[l:]<\/li><li>s1[0:l] vs s2[L-l:l] &amp;&amp; s1[l:] vs s2[0:L-l]<\/li><\/ol>\n\n\n\n<p>Time complexity: O(n^5)<br>Space complexity: O(n^4)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\nclass Solution {\npublic:\n  bool isScramble(string_view s1, string_view s2) {    \n    const int l = s1.length();        \n    if (s1 == s2) return true;\n    if (freq(s1) != freq(s2)) return false;\n    for (int i = 1; i < l; ++i)\n      if (isScramble(s1.substr(0, i), s2.substr(0, i)) \n          &#038;&#038; isScramble(s1.substr(i), s2.substr(i)) \n          || isScramble(s1.substr(0, i), s2.substr(l - i, i))\n          &#038;&#038; isScramble(s1.substr(i), s2.substr(0, l - i)))\n        return true;\n    return false;\n  }\nprivate:\n  vector<int> freq(string_view s) {\n    vector<int> f(26);\n    for (char c : s) ++f[c - 'a'];\n    return f;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\"># Author: Huahua\nclass Solution: \n  @lru_cache(maxsize=None) # optional\n  def isScramble(self, s1: str, s2: str) -&gt; bool:\n    if s1 == s2: return True\n    # important, TLE if commneted out\n    if Counter(s1) != Counter(s2): return False\n    L = len(s1)\n    for l in range(1, L):\n      if self.isScramble(s1[0:l], s2[0:l]) and self.isScramble(s1[l:], s2[l:]): \n        return True\n      if self.isScramble(s1[0:l], s2[L-l:]) and self.isScramble(s1[l:], s2[0:L-l]): \n        return True\n    return False\n\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a string&nbsp;s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of&nbsp;s1&nbsp;=&nbsp;&#8220;great&#8221;:&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[18,217,314],"class_list":["post-6481","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dp","tag-hard","tag-substring","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6481","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=6481"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6481\/revisions"}],"predecessor-version":[{"id":6492,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6481\/revisions\/6492"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6481"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6481"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6481"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}