Python - Top-Down DP
py\nfrom functools import lru_cache\n\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        \n        def buildKeyboard():\n            ro
```py\nfrom functools import lru_cache\n\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        \n        def buildKeyboard():\n            row = col = 0\n            keyboard_map = {}\n            for i in range(26):\n                row = i // 6\n                col = i % 6\n                keyboard_map[chr(i + ord(\'A\'))] = (row,col)\n            return keyboard_map\n        \n        def getCost(a, b):\n            if not a or not b:\n                return 0\n            r1, c1 = keyboard_map[a]\n            r2, c2 = keyboard_map[b]\n            return abs(r1-r2) + abs(c1-c2)\n\n        @lru_cache(None)\n        def dp(cur_idx, prev_finger1=None, prev_finger2=None):\n            if cur_idx == len(word):\n                return 0\n            finger1_cost = getCost(prev_finger1, word[cur_idx]) + dp(cur_idx+1, word[cur_idx], prev_finger2)\n            finger2_cost = getCost(prev_finger2, word[cur_idx]) + dp(cur_idx+1, prev_finger1, word[cur_idx])\n            return min(finger1_cost, finger2_cost)\n\n        keyboard_map = buildKeyboard()\n        return dp(0)\n```\nTime complexity: O(N) where n is a length of a word\nSpace compexlity: O(N)
[]