【leetcode】1138. Alphabet Board Path

题目如下：

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.

解题思路：本题难度不大，把整个表格抽象成一个坐标轴，例如a的坐标是(0,0)，l的坐标是(2,1)，那么从a到l的路径就是要左右方向上移动一次(l的x坐标减去a的x坐标)，上下的方向上移动两次(l的坐标减去a的y坐标)。这里有一点需要注意的的是起始或者终止的字符是z，因为不管是从z出发还是到达z，一定只能从经过u到达，而不能经由z的左边。

代码如下：

class Solution(object):

    def alphabetBoardPath(self, target):

        """

        :type target: str

        :rtype: str

        """

        board =  ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]

        dic = {}

        for i in range(len(board)):

            for j in range(len(board[i])):

                dic[board[i][j]] = (i,j)

        x,y = 0,0

        res = ''

        for i in target:

            x1,y1 = dic[i]

            #

            if i == 'z':

                v = y - y1

                if v > 0:

                    res += 'L' * v

                else:

                    res += 'R' * (-v)

                v = x - x1

                if v > 0:

                    res += 'U' * v

                else:

                    res += 'D' * (-v)

            else:

                v = x - x1

                if v > 0:

                    res += 'U' * v

                else:

                    res += 'D' * (-v)

                v = y - y1

                if v > 0:

                    res += 'L'*v

                else:

                    res += 'R' * (-v)

            res += '!'

            x,y = x1,y1

        return res

巴特西

【leetcode】1138. Alphabet Board Path

最新文章

热门文章