1320. Minimum Distance to Type a Word Using Two Fingers LeetCode Solution
In this guide, you will get 1320. Minimum Distance to Type a Word Using Two Fingers LeetCode Solution with the best time and space complexity. The solution to Minimum Distance to Type a Word Using Two Fingers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Distance to Type a Word Using Two Fingers
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).
Given the string word, return the minimum total distance to type such string using only two fingers.
The distance between coordinates (x1, y1) and (x2, y2) is |x1 – x2| + |y1 – y2|.
Note that the initial positions of your two fingers are considered free so do not count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.
Input: word = “CAKE”
Output: 3
Explanation: Using two fingers, one optimal way to type “CAKE” is:
Finger 1 on letter ‘C’ -> cost = 0
Finger 1 on letter ‘A’ -> cost = Distance from letter ‘C’ to letter ‘A’ = 2
Finger 2 on letter ‘K’ -> cost = 0
Finger 2 on letter ‘E’ -> cost = Distance from letter ‘K’ to letter ‘E’ = 1
Total distance = 3
Example 2:
Input: word = “HAPPY”
Output: 6
Explanation: Using two fingers, one optimal way to type “HAPPY” is:
Finger 1 on letter ‘H’ -> cost = 0
Finger 1 on letter ‘A’ -> cost = Distance from letter ‘H’ to letter ‘A’ = 2
Finger 2 on letter ‘P’ -> cost = 0
Finger 2 on letter ‘P’ -> cost = Distance from letter ‘P’ to letter ‘P’ = 0
Finger 1 on letter ‘Y’ -> cost = Distance from letter ‘A’ to letter ‘Y’ = 4
Total distance = 6
Constraints:
2 <= word.length <= 300
word consists of uppercase English letters.
Complexity Analysis
Time Complexity: O(27^2n) = O(n)
Space Complexity: O(27^2n) = O(n)
1320. Minimum Distance to Type a Word Using Two Fingers LeetCode Solution in C++
class Solution {
public:
int minimumDistance(string word) {
vector<vector<vector<int>>> mem(
, vector<vector<int>>(27, vector<int>(word.length(), -1)));
return minimumDistance(word, 26, 26, 0, mem);
}
private:
// Returns the minimum distance to type `word`, where the left finger is on
// the i-th letter, the right finger is on the j-th letter, and word[0..k)
// have been written.
int minimumDistance(const string& word, int i, int j, int k,
vector<vector<vector<int>>>& mem) {
if (k == word.length())
return 0;
if (mem[i][j][k] != -1)
return mem[i][j][k];
const int c = word[k] - 'A';
const int moveLeft = dist(i, c) + minimumDistance(word, c, j, k + 1, mem);
const int moveRight = dist(j, c) + minimumDistance(word, i, c, k + 1, mem);
return mem[i][j][k] = min(moveLeft, moveRight);
}
int dist(int a, int b) {
if (a == 26) // the first hovering state
return 0;
const int x1 = a / 6;
const int y1 = a % 6;
const int x2 = b / 6;
const int y2 = b % 6;
return abs(x1 - x2) + abs(y1 - y2);
}
}; /* code provided by PROGIEZ */
1320. Minimum Distance to Type a Word Using Two Fingers LeetCode Solution in Java
class Solution {
public int minimumDistance(String word) {
Integer[][][] mem = new Integer[27][27][word.length()];
return minimumDistance(word, 26, 26, 0, mem);
}
// Returns the minimum distance to type `word`, where the left finger is on
// the i-th letter, the right finger is on the j-th letter, and word[0..k)
// have been written.
private int minimumDistance(final String word, int i, int j, int k, Integer[][][] mem) {
if (k == word.length())
return 0;
if (mem[i][j][k] != null)
return mem[i][j][k];
final int c = word.charAt(k) - 'A';
final int moveLeft = dist(i, c) + minimumDistance(word, c, j, k + 1, mem);
final int moveRight = dist(j, c) + minimumDistance(word, i, c, k + 1, mem);
return mem[i][j][k] = Math.min(moveLeft, moveRight);
}
private int dist(int a, int b) {
if (a == 26) // the first hovering state
return 0;
final int x1 = a / 6;
final int y1 = a % 6;
final int x2 = b / 6;
final int y2 = b % 6;
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
} // code provided by PROGIEZ
1320. Minimum Distance to Type a Word Using Two Fingers LeetCode Solution in Python
class Solution:
def minimumDistance(self, word: str) -> int:
def dist(a: int, b: int) -> int:
if a == 26: # the first hovering state
return 0
x1, y1 = a // 6, a % 6
x2, y2 = b // 6, b % 6
return abs(x1 - x2) + abs(y1 - y2)
@functools.lru_cache(None)
def dp(i: int, j: int, k: int) -> int:
"""
Returns the minimum distance to type the `word`, where the left finger is
on the i-th letter, the right finger is on the j-th letter, and the
words[0..k) have been written.
"""
if k == len(word):
return 0
nxt = ord(word[k]) - ord('A')
moveLeft = dist(i, nxt) + dp(nxt, j, k + 1)
moveRight = dist(j, nxt) + dp(i, nxt, k + 1)
return min(moveLeft, moveRight)
return dp(26, 26, 0) # code by PROGIEZ
