[leetcode] 1138. Alphabet Board Path

[leetcode] 1138. Alphabet Board Path

Description

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 <= 100target consists only of English lowercase letters.

分析

题目的意思是：给定一个字符的board，和一个target字符串，求在board找到target的路径。这道题我看了别人的解法，首先从（0,0）出发到达每个字符的路径是可以通过坐标计算出来的，这样的话，我们把每个字符在board上的坐标算出来，然后求一下需要向左右上下走的步骤，就可以得出路径了。如果能想到这一点，就比较容易的写出来了。

代码

class Solution: def alphabetBoardPath(self, target: str) -> str: n=5 cx,cy=0,0 res='' offset=ord('a') for ch in target: row=(ord(ch)-offset)//n col=(ord(ch)-offset)%n if(cy>col): res+='L'*(cy-col) if(cx>row): res+='U'*(cx-row) if(cy

参考文献

​​[LeetCode] Python | O(N) | without BFS | Faster than 90% | Less space than 100%​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。