Problem statement

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

Solution

dp(f1, f2, ind) is minimum distance we can have if one finger of f1, another on f2 and we reached index ind. Actually we do not need 3 dimension, like in problem 1187 we can look at it at bipartitie graph.

Complexity

Time complexity is O(26*n), because on each level we can have at most 26 + 26 states. Space complexity is O(26).

Code

class Solution:
    def minimumDistance(self, word):
        @lru_cache(None)
        def dist(x, y):
            return abs(x // 6 - y // 6) + abs(x % 6 - y % 6)
        
        word = [ord(l) - 65 for l in word]
        dp = {(i, j): 0 for i, j in product(range(26), range(26)) if word[0] in (i, j)}
        
        for i, l in enumerate(word):
            dp2 = defaultdict(lambda: float('inf'))
            for f1, f2 in dp:
                dp2[l, f2] = min(dp2[l, f2], dp[f1, f2] + dist(f1, l))
                dp2[f1, l] = min(dp2[f1, l], dp[f1, f2] + dist(f2, l))
            dp = dp2    
        
        return min(dp.values())