What is the time complexity of LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers?

The Python solution on this page runs in O(n \times |\Sigma|^2).

What is the space complexity of LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers?

The Python solution on this page uses O(n \times |\Sigma|^2) auxiliary space.

Minimum Distance to Type a Word Using Two Fingers — LeetCode 1320 Python Solution

HardStringDynamic Programming

Problem: #1320
Pattern: Dynamic Programming
Reading time: 5 min
Source: leetcode.com

The problem

You have a keyboard layout as shown above in the X-Y plane, where each English uppercase letter is located at some coordinate. For example, the letter 'A' is located at coordinate (0, 0), the letter 'B' is located at coordinate (0, 1), the letter 'P' is located at coordinate (2, 3) and the letter 'Z' is located at coordinate (4, 1).

Example

Input: word = "CAKE"
Output: 3
Explanation: Using two fingers, one optimal way to type "CAKE" is:

Python solution

Python

class Solution:
    def minimumDistance(self, word: str) -> int:
        def dist(a: int, b: int) -> int:
            x1, y1 = divmod(a, 6)
            x2, y2 = divmod(b, 6)
            return abs(x1 - x2) + abs(y1 - y2)

        n = len(word)
        f = [[[inf] * 26 for _ in range(26)] for _ in range(n)]
        for j in range(26):
            f[0][ord(word[0]) - ord('A')][j] = 0
            f[0][j][ord(word[0]) - ord('A')] = 0
        for i in range(1, n):
            a, b = ord(word[i - 1]) - ord('A'), ord(word[i]) - ord('A')
            d = dist(a, b)
            for j in range(26):
                f[i][b][j] = min(f[i][b][j], f[i - 1][a][j] + d)
                f[i][j][b] = min(f[i][j][b], f[i - 1][j][a] + d)
                if j == a:
                    for k in range(26):
                        t = dist(k, b)
                        f[i][b][j] = min(f[i][b][j], f[i - 1][k][a] + t)
                        f[i][j][b] = min(f[i][j][b], f[i - 1][a][k] + t)
        a = min(f[n - 1][ord(word[-1]) - ord('A')])
        b = min(f[n - 1][j][ord(word[-1]) - ord('A')] for j in range(26))
        return int(min(a, b))

Complexity

Measure	Complexity
Time	O(n \times \|\Sigma\|^2)
Space	O(n \times \|\Sigma\|^2) auxiliary

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers?: LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers is rated Hard on LeetCode.
What is the time complexity of LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers?: The Python solution on this page runs in O(n \times |\Sigma|^2).
What is the space complexity of LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers?: The Python solution on this page uses O(n \times |\Sigma|^2) auxiliary space.
What topics does LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers cover?: LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers is tagged String and Dynamic Programming on LeetCode.