Python | Top Down Dynamic Programming
At each character of the word, we can choose to use left finger or right finger. When a finger hasn\'t been used before, then the cost of using that finger is 0
At each character of the word, we can choose to use left finger or right finger. When a finger hasn\'t been used before, then the cost of using that finger is 0. We calculate the cost of using left finger and right finger. If left finger has been used, update the left finger to be the current character, while keeping the right finger where it was before. If right finger has been used, update the position of the right finger to the current character and keep the left finger where it was before. Add the distance calculated to respected recursive calls and return the minimum of the two.\n\nEach recursive call created two more recursive calls, so without memoizing, the runtime would be 2 to the power of n, where n is the number of characters, since for each character, we can either use left of right finger. But since we memoize each call, we don\'t have to calculate the distance to the characters using the same fingers again. So for each character, we just compute the distance of using left finger and right finger so the time complexity is O(N) and space complexity is also O(N) to store the memoized results.\n\n```\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        board = {c: (i // 6, i % 6) for i, c in enumerate(ascii_uppercase)}\n        left = False\n        right = True\n        def calculate(start, end):\n            x1, y1 = board[start]\n            x2, y2 = board[end]\n            return abs(x1 - x2) + abs(y1 - y2)\n        def dp(left, right, i):\n            if i == len(word):\n                return 0\n            if (left, right, i) in memo:\n                return memo[(left, right, i)]\n            left_distance = calculate(left, word[i]) if left else 0\n            right_distance = calculate(right, word[i]) if right else 0\n            memo[(left, right, i)] = min(left_distance + dp(word[i], right, i + 1), \n                                         right_distance + dp(left, word[i], i + 1))\n            return memo[(left, right, i)]\n        memo = {}\n        return dp(None, None, 0)\n```
['Dynamic Programming', 'Python']