Learning On the Way

1320. Minimum Distance to Type a Word Using Two Fingers

def minimumDistance(self, word: str) -> int: 
    orda = ord('A') 
    pos = {} 
    for i in range(26): 
        pos[chr(orda + i)] = divmod(i, 6) 
         
    N = len(word) 
     
    def dist(i, j): 
        if i == 0 or j == 0: 
            return 0 
        a, b = word[i - 1], word[j - 1] 
        i1, j1 = pos[a] 
        i2, j2 = pos[b] 
        return abs(i1 - i2) + abs(j1 - j2) 
     
    dp = [[0] * (N + 1) for _ in range(N + 1)] 
     
    # Because of symmetry, dp[i][j] represent the minimum total distance when the current position is at i (so one finger must be at i-th letter) and another figure is at j-th letter. Here we label the first letter in the sequence as 1. So the maximum value of i is N. 0 is reserved for the initial state. 
    # The distance value become positive only from the 2nd letter 
    for i in range(2, N + 1): 
        c = word[i - 1] 
         
        # To get to the state of (i, j) where j = 0, 1, ..., i - 2, the only possible way is to move from the figure at i - 1 to i  
        for j in range(i - 1): 
            dp[i][j] = dp[i - 1][j] + dist(i, i - 1) 
        # To get to the state of (i, i - 1), the last state can be (i - 1, k) where k can be 0, 1, ..., i - 2  
        dp[i][i - 1] = min([(dp[i - 1][k] + dist(i, k)) for k in range(i - 1)]) 
         
    # dp[N][N] is not a valid state 
    return min(dp[-1][:N])