1320.py

# https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/

from string import ascii_uppercase

class Solution:
    
    def __init__(self):
        anchor = ord('A')
        self.keyboard = {c: ((ord(c) - anchor) // 6, (ord(c) - anchor) % 6) for c in ascii_uppercase}
        self.memo = {}
        self.distance = lambda x, y: abs(self.keyboard[x][0] - self.keyboard[y][0]) + abs(
            self.keyboard[x][1] - self.keyboard[y][1])

    def reset(self):
        self.memo = {}

    def minimumDistance(self, word):
        def r_type_word(left_hand_in, right_hand_in, word_cursor, steps):
            hash_key = f'{left_hand_in}-{right_hand_in}-{word_cursor}-{steps}'
            if hash_key in self.memo:
                return self.memo[hash_key]

            if word_cursor == len(word):
                ret = steps
            else:
                char = word[word_cursor]
                word_cursor += 1

                ret = min(
                    r_type_word(char, right_hand_in, word_cursor,
                                steps + (0 if not left_hand_in or left_hand_in == char
                                         else self.distance(left_hand_in, char))),

                    r_type_word(left_hand_in, char, word_cursor,
                                steps + (0 if not right_hand_in or right_hand_in == char
                                         else self.distance(right_hand_in, char)))
                )

            self.memo[hash_key] = ret
            return ret

        return r_type_word(None, None, 0, 0)


import unittest

class UnitTest(unittest.TestCase):

    def test(self):
        s = Solution()
        self.assertEqual(s.minimumDistance('CAKE'), 3)
        s.reset()

        self.assertEqual(s.minimumDistance('HAPPY'), 6)
        s.reset()

        self.assertEqual(s.minimumDistance('NEW'), 3)
        s.reset()

        self.assertEqual(s.minimumDistance('YEAR'), 7)
        s.reset()

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