class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        #TC: O(len(target))
        #SC: O(26)

        #Use hashmap to store locs of each chars
        #be aware of the 'z'

        Dict = {}
        for c in string.ascii_lowercase:
            TotalIdx = ord(c) - ord('a')
            RowIdx = TotalIdx // 5
            ColIdx = TotalIdx % 5
            Dict[c] = (RowIdx, ColIdx)

        start = 'a'
        i = 0
        res = ''

        while i < len(target):
            if target[i] == start:
                res += '!'
            else:
                x0, y0 = Dict[start]
                x1, y1 = Dict[target[i]]

                dx = x1 - x0
                dy = y1 - y0

                if target[i] != 'z':
                    if dx > 0:
                        res = res + 'D'*abs(dx)
                    else:
                        res = res + 'U'*abs(dx)

                    if dy > 0:
                        res = res + 'R'*abs(dy)
                    else:
                        res = res + 'L'*abs(dy)
                else:
                    res = res + 'D'*(dx-1) + 'L'*abs(dy) + 'D'

                res += '!'

            start = target[i]
            i += 1

        return res