{"id":5357,"date":"2019-07-27T21:20:52","date_gmt":"2019-07-28T04:20:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5357"},"modified":"2019-07-27T21:26:30","modified_gmt":"2019-07-28T04:26:30","slug":"leetcode-1138-alphabet-board-path","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-1138-alphabet-board-path\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1138. Alphabet Board Path"},"content":{"rendered":"\n<p>On an alphabet board, we start at position&nbsp;<code>(0, 0)<\/code>, corresponding to character&nbsp;<code>board[0][0]<\/code>.<\/p>\n\n\n\n<p>Here,&nbsp;<code>board = [\"abcde\", \"fghij\", \"klmno\", \"pqrst\", \"uvwxy\", \"z\"]<\/code>.<\/p>\n\n\n\n<p>We may make the following moves:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>'U'<\/code>&nbsp;moves our position up one row, if the square exists;<\/li><li><code>'D'<\/code>&nbsp;moves our position down one row, if the square exists;<\/li><li><code>'L'<\/code>&nbsp;moves our position left one column, if the square exists;<\/li><li><code>'R'<\/code>&nbsp;moves our position right one column, if the square exists;<\/li><li><code>'!'<\/code>&nbsp;adds the character&nbsp;<code>board[r][c]<\/code>&nbsp;at our current position&nbsp;<code>(r, c)<\/code>&nbsp;to the&nbsp;answer.<\/li><\/ul>\n\n\n\n<p>Return a sequence of moves that makes our answer equal to&nbsp;<code>target<\/code>&nbsp;in the minimum number of moves.&nbsp; You may return any path that does so.<\/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> target = \"leet\"\n<strong>Output:<\/strong> \"DDR!UURRR!!DDD!\"\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> target = \"code\"\n<strong>Output:<\/strong> \"RR!DDRR!UUL!R!\"\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= target.length &lt;= 100<\/code><\/li><li><code>target<\/code>&nbsp;consists only of English lowercase letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Manhattan walk<\/strong><\/h2>\n\n\n\n<p>Compute the coordinates of each char, walk from (x1, y1) to (x2, y2) in Manhattan way. <br><strong>Be aware of the last row, we can only walk on &#8216;z&#8217;, so go left and up first if needed.<\/strong><\/p>\n\n\n\n<p>Time complexity: O(26*26 + n)<br>Space complexity: O(26*26)<\/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\nclass Solution {\npublic:\n  string alphabetBoardPath(string target) {    \n    vector<vector<string>> paths(26, vector<string>(26));\n    for (int s = 0; s < 26; ++s)\n      for (int t = 0; t < 26; ++t) {\n        int dx = t % 5 - s % 5;\n        int dy = t \/ 5 - s \/ 5; \n        string path;\n        while (dx < 0) { path.push_back('L'); dx++; }\n        while (dy < 0) { path.push_back('U'); dy++; }\n        while (dx > 0) { path.push_back('R'); dx--; }\n        while (dy > 0) { path.push_back('D'); dy--; }\n        paths[s][t] = path;\n      }\n    \n    char l = 'a';\n    string ans;\n    for (char c : target) {\n      ans += paths[l - 'a'][c - 'a'] + \"!\";\n      l = c;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>On an alphabet board, we start at position&nbsp;(0, 0), corresponding to character&nbsp;board[0][0]. Here,&nbsp;board = [&#8220;abcde&#8221;, &#8220;fghij&#8221;, &#8220;klmno&#8221;, &#8220;pqrst&#8221;, &#8220;uvwxy&#8221;, &#8220;z&#8221;]. We may make the following&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127],"tags":[177,87,4],"class_list":["post-5357","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-medium","tag-shortest-path","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5357","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=5357"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5357\/revisions"}],"predecessor-version":[{"id":5359,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5357\/revisions\/5359"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5357"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5357"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5357"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}