{"id":596,"date":"2017-10-15T10:29:41","date_gmt":"2017-10-15T17:29:41","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=596"},"modified":"2018-04-19T08:37:38","modified_gmt":"2018-04-19T15:37:38","slug":"leetcode-72-edit-distance","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-72-edit-distance\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 72. Edit Distance"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 72. Edit Distance - \u5237\u9898\u627e\u5de5\u4f5c EP87\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/Q4i_rqON2-E?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 words\u00a0<i>word1<\/i>\u00a0and\u00a0<i>word2<\/i>, find the minimum number of steps required to convert\u00a0<i>word1<\/i>\u00a0to\u00a0<i>word2<\/i>. (each operation is counted as 1 step.)<\/p>\n<p>You have the following 3 operations permitted on a word:<\/p>\n<p>a) Insert a character<br \/>\nb) Delete a character<br \/>\nc) Replace a character<\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>Dynamic Programming<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/72-ep87.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-602\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/72-ep87.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/72-ep87.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/72-ep87-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/72-ep87-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/72-ep87-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>Recursive<\/p>\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 13 ms\r\nclass Solution {\r\npublic:\r\n    int minDistance(string word1, string word2) {\r\n        int l1 = word1.length();\r\n        int l2 = word2.length();\r\n        d_ = vector&lt;vector&lt;int&gt;&gt;(l1 + 1, vector&lt;int&gt;(l2 + 1, -1));\r\n        return minDistance(word1, word2, l1, l2);\r\n    }\r\nprivate:\r\n    vector&lt;vector&lt;int&gt;&gt; d_;\r\n    \/\/ minDistance from word1[0:l1-1] to word2[0:l2-1]\r\n    int minDistance(const string&amp; word1, const string&amp; word2, int l1, int l2) {\r\n        if (l1 == 0) return l2;\r\n        if (l2 == 0) return l1;\r\n        if (d_[l1][l2] &gt;= 0) return d_[l1][l2];\r\n        \r\n        int ans;\r\n        if (word1[l1 - 1] == word2[l2 - 1])\r\n            ans = minDistance(word1, word2, l1 - 1, l2 - 1);\r\n        else \r\n            ans = min(minDistance(word1, word2, l1 - 1, l2 - 1),\r\n                  min(minDistance(word1, word2, l1 - 1, l2), \r\n                      minDistance(word1, word2, l1, l2 - 1))) + 1;\r\n        \r\n        return d_[l1][l2] = ans;        \r\n    }\r\n};<\/pre>\n<p>Iterative<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 9 ms\r\nclass Solution {\r\npublic:\r\n    int minDistance(string word1, string word2) {\r\n        int l1 = word1.length();\r\n        int l2 = word2.length();\r\n        \/\/ d[i][j] := minDistance(word1[0:i - 1], word2[0:j - 1]);\r\n        vector&lt;vector&lt;int&gt;&gt; d(l1 + 1, vector&lt;int&gt;(l2 + 1, 0));\r\n        \r\n        for (int i = 0; i &lt;= l1; ++i)\r\n            d[i][0] = i;\r\n        for (int j = 0; j &lt;= l2; ++j)\r\n            d[0][j] = j;\r\n        \r\n        for (int i = 1; i &lt;= l1; ++i)\r\n            for (int j = 1; j &lt;= l2; ++j) {\r\n                int c = (word1[i - 1] == word2[j - 1]) ? 0 : 1;\r\n                d[i][j] = min(d[i - 1][j - 1] + c, \r\n                              min(d[i][j - 1], d[i - 1][j]) + 1);\r\n            }\r\n        \r\n        return d[l1][l2];\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Given two words\u00a0word1\u00a0and\u00a0word2, find the minimum number of steps required to convert\u00a0word1\u00a0to\u00a0word2. (each operation is counted as 1 step.) You have the following 3&#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":[130,18,4],"class_list":["post-596","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-distance","tag-dp","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/596","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=596"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/596\/revisions"}],"predecessor-version":[{"id":2649,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/596\/revisions\/2649"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=596"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=596"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=596"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}