1320. Minimum Distance to Type a Word Using Two Fingers

Information

  • Diffculty: Hard

  • Created: 2020-01-12 16:26:27

  • Last Motified: 2020-01-12 16:26:27

  • Tags: Dynamic Programming

Intuition

In this problem, we have 2 finger left and right. For each character, we could use either left finder or right finger to push the key. Since the number of characters is 2 - 300, there are totally 2 ^ 300 possible situations. So the brute force solution would failed with Time Limit Exceeded.

Now let’s consider solving it using DP. For each character in the given string, there are several possible states where each finger is located on one position. For next character, we could get 2 possible states from every current state.

For example, state DP[i][x][y] is the minimum cost for solving string s[:i] and left finger on x and right finger on y. Then DP[i + 1][m][n] is the minimum value of DP[i][x][y] + distance(x, y, m, n) for all possible x and y.

Solution

import string


class Solution:
    ROW = 6

    def index(self, c):
        return ord(c) - ord('A')

    def coordinate(self, index):
        return index % self.ROW, index // self.ROW

    def distance(self, i, j):
        x1, y1 = self.coordinate(i)
        x2, y2 = self.coordinate(j)
        return abs(x1 - x2) + abs(y1 - y2)

    def minimumDistance(self, word: str) -> int:
        distance = {}
        for i in range(26):
            for j in range(26):
                distance[(i, j)] = 0

        for c in word:
            index = self.index(c)
            tmp = {}
            for (i, j), v in distance.items():
                if (i, index) not in tmp:
                    tmp[(i, index)] = v + self.distance(j, index)
                else:
                    tmp[(i, index)] = min(
                        tmp[(i, index)],
                        v + self.distance(j, index)
                    )
                if (index, j) not in tmp:
                    tmp[(index, j)] = v + self.distance(i, index)
                else:
                    tmp[(index, j)] = min(
                        tmp[(index, j)],
                        v + self.distance(i, index)
                    )
                distance = tmp
        return min(distance.values())