Alphabet Board Path

Problem Id: 1138 Difficulty: Medium


Intuition

Solution


class Solution(object):
    def alphabetBoardPath(self, target):
        """
        :type target: str
        :rtype: str
        """
        board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]
        position = {}
        for i in range(len(board)):
            for j in range(len(board[i])):
                position[board[i][j]] = [i, j]

        i, j = 0, 0
        index = 0
        ans = []
        while index < len(target):
            c = target[index]
            index += 1
            next_i, next_j = position[c]
            if i > next_i:
                ans.extend(['U'] * (i - next_i))
            if next_i > i:
                if next_i == 5:
                    ans.extend(['D'] * (4 - i))
                else:
                    ans.extend(['D'] * (next_i - i))
            if j > next_j:
                ans.extend(['L'] * (j - next_j))
            if next_j > j:
                ans.extend(['R'] * (next_j - j))
            if next_i == 5 and next_i > i:
                ans.append('D')
            ans.append('!')
            i, j = next_i, next_j
        return ''.join(ans)


# TestCode
import unittest


class TestSolution(unittest.TestCase):
    def test_solution(self):
        self.assertEqual(
            Solution().alphabetBoardPath('leet'),
            "DDR!UURRR!!DDD!"
        )

    def test_solution2(self):
        self.assertEqual(
            Solution().alphabetBoardPath('code'),
            "RR!DDRR!UUL!R!"
        )

    def test_solution4(self):
        self.assertEqual(
            Solution().alphabetBoardPath('zdz'),
            "DDDDD!UUUUURRR!DDDDLLLD!"
        )


if __name__ == '__main__':
    unittest.main()