Problem statement

https://leetcode.com/problems/alphabet-board-path/

Solution

Just simulate process, also be careful with letter Z, we need order of traversal L D U R to not go out of grid.

Complexity

It is O(n*10) for time and space, because it is the length of the longest possible path.

Code

class Solution:
    def alphabetBoardPath(self, target):
        coords = lambda x: divmod(ord(x) - 97, 5)
        ans = []
        for l1, l2 in zip("a" + target, target):
            y1, x1 = coords(l1)
            y2, x2 = coords(l2)
            if x2 < x1: ans += ["L"] * (x1 - x2)
            if y1 < y2: ans += ["D"] * (y2 - y1)
            if y2 < y1: ans += ["U"] * (y1 - y2)
            if x1 < x2: ans += ["R"] * (x2 - x1)
            ans += ["!"]
        return "".join(ans)