{"id":3450,"date":"2018-08-05T22:41:30","date_gmt":"2018-08-06T05:41:30","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3450"},"modified":"2018-08-05T22:57:34","modified_gmt":"2018-08-06T05:57:34","slug":"leetcode-97-interleaving-string","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-97-interleaving-string\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 97. Interleaving String"},"content":{"rendered":"<h1><strong>Problem<\/strong><\/h1>\n<p>Given\u00a0<em>s1<\/em>,\u00a0<em>s2<\/em>,\u00a0<em>s3<\/em>, find whether\u00a0<em>s3<\/em>\u00a0is formed by the interleaving of\u00a0<em>s1<\/em>\u00a0and\u00a0<em>s2<\/em>.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input:<\/strong> s1 = \"aabcc\", s2 = \"dbbca\", <em>s3<\/em> = \"aadbbcbcac\"\r\n<strong>Output:<\/strong> true\r\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input:<\/strong> s1 = \"aabcc\", s2 = \"dbbca\", <em>s3<\/em> = \"aadbbbaccc\"\r\n<strong>Output:<\/strong> false\r\n<\/pre>\n<h1><strong>Solution: DP<\/strong><\/h1>\n<p>Subproblems : whether s3[0:i+j] can be formed by interleaving s1[0:i] and s2[0:j].<\/p>\n<p>Time complexity: O(mn)<\/p>\n<p>Space complexity: O(mn)<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huhaua\r\n\/\/ Running time: 0 ms\r\nclass Solution {\r\npublic:\r\n  bool isInterleave(string s1, string s2, string s3) {\r\n    int l1 = s1.length();\r\n    int l2 = s2.length();\r\n    int l3 = s3.length();\r\n    if (l1 + l2 != l3) return false;\r\n    \/\/ dp[i][j]: whehter s3[0:i+j] is a interleva of s1[0:i] and s2[0:j]\r\n    vector&lt;vector&lt;int&gt;&gt; dp(l1 + 1, vector&lt;int&gt;(l2 + 1));\r\n    dp[0][0] = true;\r\n    for (int i = 0; i &lt;= l1; ++i)\r\n      for (int j = 0; j &lt;= l2; ++j) {        \r\n        if (i &gt; 0) dp[i][j] |= dp[i - 1][j] &amp;&amp; s1[i - 1] == s3[i + j - 1];\r\n        if (j &gt; 0) dp[i][j] |= dp[i][j - 1] &amp;&amp; s2[j - 1] == s3[i + j - 1];        \r\n      }\r\n    return dp[l1][l2];\r\n  }\r\n};<\/pre>\n<p>Recursion + Memorization<\/p>\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 0 ms\r\nclass Solution {\r\npublic:\r\n  bool isInterleave(string s1, string s2, string s3) {\r\n    m_ = vector&lt;vector&lt;int&gt;&gt;(s1.length() + 1, vector&lt;int&gt;(s2.length() + 1, INT_MIN));\r\n    return dp(s1, s1.length(), s2, s2.length(), s3, s3.length());\r\n  }\r\nprivate:\r\n  \/\/ m_[i][j]: whehter s3[0:i+j] is a interleva of s1[0:i] and s2[0:j]\r\n  vector&lt;vector&lt;int&gt;&gt; m_;\r\n  \r\n  bool dp(const string&amp; s1, int l1, const string&amp; s2, int l2, const string&amp; s3, int l3) {\r\n    if (l1 + l2 != l3) return false;\r\n    if (l1 == 0 &amp;&amp; l2 == 0) return true;\r\n    if (m_[l1][l2] != INT_MIN) return m_[l1][l2];\r\n    if (l1 &gt; 0 &amp; s3[l3 - 1] == s1[l1 - 1] &amp;&amp; dp(s1, l1 - 1, s2, l2, s3, l3 - 1)\r\n      ||l2 &gt; 0 &amp; s3[l3 - 1] == s2[l2 - 1] &amp;&amp; dp(s1, l1, s2, l2 - 1, s3, l3 - 1))\r\n      m_[l1][l2] = 1;\r\n    else\r\n      m_[l1][l2] = 0;\r\n    return m_[l1][l2];\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given\u00a0s1,\u00a0s2,\u00a0s3, find whether\u00a0s3\u00a0is formed by the interleaving of\u00a0s1\u00a0and\u00a0s2. Example 1: Input: s1 = &#8220;aabcc&#8221;, s2 = &#8220;dbbca&#8221;, s3 = &#8220;aadbbcbcac&#8221; Output: true Example 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":[46],"tags":[18,365,366,4],"class_list":["post-3450","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-interleaving","tag-omn","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3450","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=3450"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3450\/revisions"}],"predecessor-version":[{"id":3455,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3450\/revisions\/3455"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3450"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3450"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3450"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}