Minimum Distance to Type a Word Using Two Fingers LeetCode solution in Python

1
from functools import cache
2

3

4
class Solution:
5
    def minimumDistance(self, word: str) -> int:
6
        alphabets = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
7
        COL = 6
8
        index = {c: (i // COL, i % COL) for i, c in enumerate(alphabets)}
9

10
        def dist(a, b):
11
            return abs(index[a][0] - index[b][0]) + abs(index[a][1] - index[b][1])
12

13
        @cache
14
        def dfs(lhand, rhand, i):
15
            if i == len(word):
16
                return 0
17
            res = float("inf")
18
            res = (
19
                min(res, dfs(word[i], rhand, i + 1))
20
                if lhand == -1
21
                else min(res, dist(lhand, word[i]) + dfs(word[i], rhand, i + 1))
22
            )
23
            res = (
24
                min(res, dfs(lhand, word[i], i + 1))
25
                if rhand == -1
26
                else min(res, dist(word[i], rhand) + dfs(lhand, word[i], i + 1))
27
            )
28
            return res
29

30
        return dfs(-1, -1, 0)