{"id":3236,"date":"2018-07-20T23:51:23","date_gmt":"2018-07-21T06:51:23","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3236"},"modified":"2018-07-22T01:35:48","modified_gmt":"2018-07-22T08:35:48","slug":"leetcode-712-minimum-ascii-delete-sum-for-two-strings","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-712-minimum-ascii-delete-sum-for-two-strings\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 712. Minimum ASCII Delete Sum for Two Strings"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 712. Minimum ASCII Delete Sum for Two Strings - \u5237\u9898\u627e\u5de5\u4f5c EP209\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/RFBWavPKCJg?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<h1><strong>Problem<\/strong><\/h1>\n<p>Given two strings\u00a0<code>s1, s2<\/code>, find the lowest ASCII sum of deleted characters to make two strings equal.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"crayon:false\"><b>Input:<\/b> s1 = \"sea\", s2 = \"eat\"\r\n<b>Output:<\/b> 231\r\n<b>Explanation:<\/b> Deleting \"s\" from \"sea\" adds the ASCII value of \"s\" (115) to the sum.\r\nDeleting \"t\" from \"eat\" adds 116 to the sum.\r\nAt the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.\r\n<\/pre>\n<p><b>Example 2:<\/b><\/p>\n<pre class=\"crayon:false\"><b>Input:<\/b> s1 = \"delete\", s2 = \"leet\"\r\n<b>Output:<\/b> 403\r\n<b>Explanation:<\/b> Deleting \"dee\" from \"delete\" to turn the string into \"let\",\r\nadds 100[d]+101[e]+101[e] to the sum.  Deleting \"e\" from \"leet\" adds 101[e] to the sum.\r\nAt the end, both strings are equal to \"let\", and the answer is 100+101+101+101 = 403.\r\nIf instead we turned both strings into \"lee\" or \"eet\", we would get answers of 433 or 417, which are higher.\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ul>\n<li><code>0 &lt; s1.length, s2.length &lt;= 1000<\/code>.<\/li>\n<li>All elements of each string will have an ASCII value in\u00a0<code>[97, 122]<\/code>.<\/li>\n<\/ul>\n<h1><strong>Solution: DP<\/strong><\/h1>\n<p>Time complexity: O(l1 * l2)<\/p>\n<p>Space complexity:\u00a0O(l1 * l2)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 8 ms\r\nclass Solution {\r\npublic:\r\n  int minimumDeleteSum(string s1, string s2) {\r\n    const int l1 = s1.length();\r\n    const int l2 = s2.length();\r\n    \/\/ dp[i][j] := min delete sum of (s1.substr(0, i), s2.substr(0, j))\r\n    vector&lt;vector&lt;int&gt;&gt; dp(l1 + 1, vector&lt;int&gt;(l2 + 1));\r\n    for (int i = 1; i &lt;= l1; ++i)\r\n      dp[i][0] = dp[i - 1][0] + s1[i - 1];\r\n    for (int j = 1; j &lt;= l2; ++j)\r\n      dp[0][j] = dp[0][j - 1] + s2[j - 1];    \r\n    for (int i = 1; i &lt;= l1; ++i)\r\n      for (int j = 1; j &lt;= l2; ++j)\r\n        if (s1[i - 1] == s2[j - 1])\r\n          \/\/ keep s1[i - 1] and s2[j - 1]\r\n          dp[i][j] = dp[i - 1][j - 1]; \r\n        else\r\n          dp[i][j] = min(dp[i - 1][j] + s1[i - 1],  \/\/ delete s1[i - 1]\r\n                         dp[i][j - 1] + s2[j - 1]); \/\/ delete s2[j - 1]\r\n    return dp[l1][l2];\r\n  }\r\n};<\/pre>\n<h1><strong>Solution2: Recursion + Memorization<\/strong><\/h1>\n<p>Time complexity: O(l1 * l2)<\/p>\n<p>Space complexity: O(l1 * l2)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 20 ms\r\nclass Solution {\r\npublic:\r\n  int minimumDeleteSum(string s1, string s2) {\r\n    const int l1 = s1.length();\r\n    const int l2 = s2.length();\r\n    m_ = vector&lt;vector&lt;int&gt;&gt;(l1 + 1, vector&lt;int&gt;(l2 + 1, INT_MAX));\r\n    return dp(s1, l1, s2, l2);\r\n  }\r\nprivate:\r\n  int dp(const string&amp; s1, int i, const string&amp; s2, int j) {\r\n    if (i == 0 &amp;&amp; j == 0) return 0;\r\n    if (m_[i][j] != INT_MAX) return m_[i][j];\r\n    if (i == 0) \/\/ s1 is empty.\r\n      return m_[i][j] = dp(s1, i, s2, j - 1) + s2[j - 1];\r\n    if (j == 0) \/\/ s2 is empty\r\n      return m_[i][j] = dp(s1, i - 1, s2, j) + s1[i - 1];\r\n    if (s1[i - 1] == s2[j - 1]) \/\/ skip s1[i-1] \/ s2[j-1]\r\n      return m_[i][j] = dp(s1, i - 1, s2, j - 1);\r\n    return m_[i][j] = min(dp(s1, i - 1, s2, j) + s1[i - 1],  \/\/ del s1[i-1]\r\n                          dp(s1, i, s2, j - 1) + s2[j - 1]); \/\/ del s2[j-1]\r\n  }  \r\n  vector&lt;vector&lt;int&gt;&gt; m_;\r\n};<\/pre>\n<h1><strong>Related Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-72-edit-distance\/\">\u82b1\u82b1\u9171 LeetCode 72. Edit Distance<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-115-distinct-subsequences\/\">\u82b1\u82b1\u9171 LeetCode 115. Distinct Subsequences<\/a><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given two strings\u00a0s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal. Example 1: Input: s1 = &#8220;sea&#8221;, s2&#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":[344,274,18,4],"class_list":["post-3236","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-ascii","tag-delete","tag-dp","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3236","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=3236"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3236\/revisions"}],"predecessor-version":[{"id":3251,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3236\/revisions\/3251"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3236"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3236"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3236"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}