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 characterboard[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 }
标签:1138,target,Alphabet,字母,sb,board,Path,position,moves From: https://www.cnblogs.com/cnoodle/p/17121341.html