首页 > 其他分享 >[LeetCode] 1138. Alphabet Board Path

[LeetCode] 1138. Alphabet Board Path

时间:2023-02-15 00:55:04浏览次数:61  
标签:1138 target Alphabet 字母 sb board Path position moves

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"], as shown in the diagram below.

We may make the following moves:

  • 'U' moves our position up one row, if the position exists on the board;
  • 'D' moves our position down one row, if the position exists on the board;
  • 'L' moves our position left one column, if the position exists on the board;
  • 'R' moves our position right one column, if the position exists on the board;
  • '!' adds the character board[r][c] at our current position (r, c) to the answer.

(Here, the only positions that exist on the board are positions with letters on them.)

Return a sequence of moves that makes our answer equal to target in the minimum number of moves.  You may return any path that does so.

Example 1:

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"

Example 2:

Input: target = "code"
Output: "RR!DDRR!UUL!R!"

Constraints:

  • 1 <= target.length <= 100
  • target consists only of English lowercase letters.

字母板上的路径。

我们从一块字母板上的位置 (0, 0) 出发,该坐标对应的字符为 board[0][0]。

在本题里,字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"],如下所示。

我们可以按下面的指令规则行动:

如果方格存在,'U' 意味着将我们的位置上移一行;
如果方格存在,'D' 意味着将我们的位置下移一行;
如果方格存在,'L' 意味着将我们的位置左移一列;
如果方格存在,'R' 意味着将我们的位置右移一列;
'!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。
(注意,字母板上只存在有字母的位置。)

返回指令序列,用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/alphabet-board-path
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这是一道字符串的题,唯一需要注意的是走到字母Z和从字母Z走到别处的方式。因为字母Z在第五行 (index 从 0 开始),所以如果从别处走到第五行的话,需要先走到第一列再往下走,否则就会走到 board 的外面。同样的,如果是从字母 Z 往别的地方走,需要先往上,才能往右走。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public String alphabetBoardPath(String target) {
 3         StringBuilder sb = new StringBuilder();
 4         int i = 0;
 5         int j = 0;
 6         for (int k = 0; k < target.length(); k++) {
 7             int letter = target.charAt(k) - 'a';
 8             int x = letter / 5;
 9             int y = letter % 5;
10             while (i > x) {
11                 sb.append('U');
12                 i--;
13             }
14             while (j < y) {
15                 sb.append('R');
16                 j++;
17             }
18             while (j > y) {
19                 sb.append('L');
20                 j--;
21             }
22             while (i < x) {
23                 sb.append('D');
24                 i++;
25             }
26             sb.append('!');
27         }
28         return sb.toString();
29     }
30 }

 

LeetCode 题目总结

标签:1138,target,Alphabet,字母,sb,board,Path,position,moves
From: https://www.cnblogs.com/cnoodle/p/17121341.html

相关文章

  • ubuntu上配置multipath
    参考https://www.cnblogs.com/pengdonglin137/p/17115545.htmlhttps://blog.51cto.com/u_5041419/4728883步骤上文中在ubuntu下搭建了iscsi存储,下面基于iscsi存储创......
  • 1138.alphabet-board-path 字母板上的路径
    问题描述1138.字母板上的路径解题思路考虑到'z'单独在一个地方,因此移动顺序中,左下、右上不能反过来,即不能先往下再往左或者先往右再往上。代码classSolution{publi......
  • 2023-02-13 More than one file was found with OS independent path 'lib/armeabi-v7
    as工具运行rn项目报错:MorethanonefilewasfoundwithOSindependentpath'lib/armeabi-v7a/libfbjni.so'.IfyouareusingjniLibsandCMakeIMPORTEDtargets。......
  • python的几个路径 sys.argv[0],__file__,os.path.curdir
    之前写过一个关于这几个路径的帖子,找不到了,最近又因为这个路径,踩了一把坑,记录一下首先,这三个变量,都是可以用来找到当前脚本所在目录的,sys.argv是参数列表,第一个值,python......
  • 力扣---1138. 字母板上的路径
    我们从一块字母板上的位置(0,0)出发,该坐标对应的字符为board[0][0]。在本题里,字母板为board=["abcde","fghij","klmno","pqrst","uvwxy","z"],如下所示。我们可......
  • xpath提取二手房
    xpath提取二手房#利用xpath提取二手房importrequestsfromlxmlimportetreeurl='https://bj.58.com/ershoufang/'head={'user-agent':'Mozilla/5.0(WindowsN......
  • event.path参数被浏览器删除,如何一劳永逸的解决
    问题2月初,Chrome(版本号109.0.5414.120)在一次升级中删除绑定点击等等部分事件中的Event.path数组参数,(Edge和其他国产chromium内核浏览器是没有变化的),官方升级记录日......
  • pycharm导入三方库失败,导入jsonpath失败,ERROR: Error [WinError 2] 系统找不到指定的
    另一种方法,手动下载包,手动安装1,http://www.ultimate.com/phil/python/download/,下载对应的本地包2,解压文件jsonpath-XX3,打开cmd窗口4,cdjsonpath-XX,这个文件夹目录......
  • JVM classpath的理解和设置总结
    本文为博主原创,转载请注明出处:1.介绍classpath是java运行时环境搜索类和其他资源文件(比如jar\zip等资源)的路径。类路径告诉JDK工具和应用程序在哪里可以找到第三方和......
  • [AGC013B] Hamiltonish Path
    个人思路:随便从一个节点开始搜索,只要当前节点不满足条件,随便找一个与它有边相连,不在序列里的节点加入序列。因为要么中途停止,要么把所有节点遍历一遍,一定能找到一个端点。......