{"id":6080,"date":"2020-01-12T13:13:56","date_gmt":"2020-01-12T21:13:56","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6080"},"modified":"2020-01-12T21:36:27","modified_gmt":"2020-01-13T05:36:27","slug":"leetcode-1320-minimum-distance-to-type-a-word-using-two-fingers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1320-minimum-distance-to-type-a-word-using-two-fingers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers - \u5237\u9898\u627e\u5de5\u4f5c EP298\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/GRRDl3HxQAI?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<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/01\/02\/leetcode_keyboard.png\" alt=\"\"\/><\/figure>\n\n\n\n<p>You have a keyboard layout as shown above in the XY plane, where each English uppercase letter is located at some coordinate, for example, the letter&nbsp;<strong>A<\/strong>&nbsp;is located at coordinate&nbsp;<strong>(0,0)<\/strong>, the letter&nbsp;<strong>B<\/strong>&nbsp;is located at coordinate&nbsp;<strong>(0,1)<\/strong>, the letter&nbsp;<strong>P<\/strong>&nbsp;is located at coordinate&nbsp;<strong>(2,3)<\/strong>&nbsp;and the letter&nbsp;<strong>Z<\/strong>&nbsp;is located at coordinate&nbsp;<strong>(4,1)<\/strong>.<\/p>\n\n\n\n<p>Given the string&nbsp;<code>word<\/code>, return the minimum total distance to type such string using only two&nbsp;fingers. The distance between coordinates&nbsp;<strong>(x<sub>1<\/sub>,y<sub>1<\/sub>)<\/strong>&nbsp;and&nbsp;<strong>(x<sub>2<\/sub>,y<sub>2<\/sub>)<\/strong>&nbsp;is&nbsp;<strong>|x<sub>1<\/sub>&nbsp;&#8211; x<sub>2<\/sub>| + |y<sub>1<\/sub>&nbsp;&#8211; y<sub>2<\/sub>|<\/strong>.&nbsp;<\/p>\n\n\n\n<p>Note that the initial positions of your two&nbsp;fingers are considered free so don&#8217;t count towards your total distance, also your two&nbsp;fingers do not have to start at the first letter or the first two&nbsp;letters.<\/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> word = \"CAKE\"\n<strong>Output:<\/strong> 3\n<strong>Explanation: \n<\/strong>Using two fingers, one optimal way to type \"CAKE\" is: \nFinger 1 on letter 'C' -&gt; cost = 0 \nFinger 1 on letter 'A' -&gt; cost = Distance from letter 'C' to letter 'A' = 2 \nFinger 2 on letter 'K' -&gt; cost = 0 \nFinger 2 on letter 'E' -&gt; cost = Distance from letter 'K' to letter 'E' = 1 \nTotal distance = 3\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> word = \"HAPPY\"\n<strong>Output:<\/strong> 6\n<strong>Explanation: <\/strong>\nUsing two fingers, one optimal way to type \"HAPPY\" is:\nFinger 1 on letter 'H' -&gt; cost = 0\nFinger 1 on letter 'A' -&gt; cost = Distance from letter 'H' to letter 'A' = 2\nFinger 2 on letter 'P' -&gt; cost = 0\nFinger 2 on letter 'P' -&gt; cost = Distance from letter 'P' to letter 'P' = 0\nFinger 1 on letter 'Y' -&gt; cost = Distance from letter 'A' to letter 'Y' = 4\nTotal distance = 6\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> word = \"NEW\"\n<strong>Output:<\/strong> 3\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> word = \"YEAR\"\n<strong>Output:<\/strong> 7\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= word.length &lt;= 300<\/code><\/li><li>Each&nbsp;<code>word[i]<\/code>&nbsp;is an English uppercase letter.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-1.png\" alt=\"\" class=\"wp-image-6083\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-2.png\" alt=\"\" class=\"wp-image-6084\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-3.png\" alt=\"\" class=\"wp-image-6085\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-4.png\" alt=\"\" class=\"wp-image-6086\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1230-ep298-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Top down: O(n*27^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 64 ms, 46.6 MB\nclass Solution {\npublic:\n  int minimumDistance(string word) {\n    constexpr int kRest = 26;\n    const int n = word.length();\n    vector<vector<vector<int>>> mem(n, vector<vector<int>>(27, vector<int>(27, -1)));\n    \n    auto cost = [](int c1, int c2) {\n      if (c1 == kRest) return 0;\n      return abs(c1 \/ 6 - c2 \/ 6) + abs(c1 % 6 - c2 % 6);\n    };\n    \n    \/\/ min cost to type word[i:n]. l, r are the last finger positions.\n    function<int(int, int, int)> dp = [&](int i, int l, int r) {\n      if (i == n) return 0;\n      if (mem[i][l][r] >= 0) return mem[i][l][r];\n      int c = word[i] - 'A';\n      return mem[i][l][r] = min(dp(i + 1, c, r) + cost(l, c),\n                                dp(i + 1, l, c) + cost(r, c));      \n    };\n    \n    return dp(0, kRest, kRest);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 12 ms, 10.1 MB\nclass Solution {\npublic:\n  int minimumDistance(string word) {\n    constexpr int kRest = 26;\n    const int n = word.length();\n    vector<vector<int>> mem(n, vector<int>(27));\n    \n    auto cost = [](int c1, int c2) {\n      if (c1 == kRest) return 0;\n      return abs(c1 \/ 6 - c2 \/ 6) + abs(c1 % 6 - c2 % 6);\n    };\n    \n    \/\/ min cost to type word[i:n]. o is the last position of the other finger.\n    \/\/ the current finger is at word[i - 1].\n    function<int(int, int)> dp = [&](int i, int o) {\n      if (i == n) return 0;\n      if (mem[i][o]) return mem[i][o];\n      int p = i == 0 ? kRest : word[i - 1] - 'A';\n      int c = word[i] - 'A';\n      return mem[i][o] = min(dp(i + 1, o) + cost(p, c), \/\/ same finger\n                             dp(i + 1, p) + cost(o, c)); \/\/ other finger\n    };\n    \n    return dp(0, kRest);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 8 ms, 10.1 MB\nclass Solution {\npublic:\n  int minimumDistance(string word) {\n    constexpr int kRest = 26;\n    const int n = word.length();\n       \n    \/\/ dp[i][j] : min cost to type word[0:i]\n    \/\/ one finger is at word[i - 1], another finger is at j.\n    vector<vector<int>> dp(n + 1, vector<int>(27, INT_MAX \/ 2));\n    \n    dp[0][kRest] = 0;\n    \n    auto cost = [](int c1, int c2) {\n      if (c1 == kRest) return 0;\n      return abs(c1 \/ 6 - c2 \/ 6) + abs(c1 % 6 - c2 % 6);\n    };\n    \n    for (int i = 0; i < n; ++i) {\n      int p = i == 0 ? kRest : word[i - 1] - 'A';\n      int c = word[i] - 'A';\n      for (int j = 0; j <= 26; ++j) {\n        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cost(p, c));  \/\/ same finger\n        dp[i + 1][p] = min(dp[i + 1][p], dp[i][j] + cost(j, c)); \/\/ other finger\n      }\n    }\n    \n    return *min_element(begin(dp[n]), end(dp[n]));\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You have a keyboard layout as shown above in the XY plane, where each English uppercase letter is located at some coordinate, for example, the&#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,217],"class_list":["post-6080","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6080","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=6080"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6080\/revisions"}],"predecessor-version":[{"id":6089,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6080\/revisions\/6089"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6080"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6080"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6080"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}