LeetCode 1320: Minimum Distance to Type a Word Using Two Fingers II

I'm posting my Python code for LeetCode's 1320. If you have time and would like to review, please do so.

Problem

• You have a keyboard layout as shown above in the XY 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 $$\(x_1,y_1)\$$ and $$\(x_2,y_2)\$$ is $$\|x_1 - x_2| + |y_1 - y_2|\$$.

• Note that the initial positions of your two fingers are considered free so don't count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.

Example 1:

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

Constraints:

• $$\2 \le \text{word.length} \le 300\$$
• Each word[i] is an English uppercase letter.

Accepted Python

import string
import functools

class Solution:
def minimumDistance(self, word: str) -> int:
WIDTH = 6
A_DECIMAL = 65
def get_coordinates(left: int, right: int) -> int:
if not left or not right:
return 0

x_left, y_left = indices[left]
x_right, y_right = indices[right]

return abs(x_left - x_right) + abs(y_left - y_right)

@functools.lru_cache(None)
def get_dp(index, word_a: str = None, word_b: str = None) -> None:
if index == len(chars):
return 0

dist_a = get_coordinates(word_a, chars[index]) + get_dp(index + 1, chars[index], word_b)
dist_b = get_coordinates(word_b, chars[index]) + get_dp(index + 1, word_a, chars[index])

return min(dist_a, dist_b)

chars = ''.join(a for a, b in zip(word, word[1:] + ' ') if a != b)
indices = {char: divmod((ord(char) - A_DECIMAL), WIDTH) for char in string.ascii_uppercase}
return get_dp(0)


Reference

On LeetCode, there is a class usually named Solution with one or more public functions which we are not allowed to rename.

Some remarks

A_DECIMAL and it's use

A_DECIMAL = 65
# [...]
indices = {char: divmod((ord(char) - A_DECIMAL), WIDTH) for char in string.ascii_uppercase}


there is nothing wrong with

ord('A')


which you can use inline without defining a global (which it is not in the required Solution context). You can even get rid of the ord math by enumerating.

indices = {char: divmod(idx, WIDTH) for idx, char in enumerate(string.ascii_uppercase)}


Names

def get_coordinates(left: int, right: int) -> int:
if not left or not right:
return 0

x_left, y_left = indices[left]
x_right, y_right = indices[right]

return abs(x_left - x_right) + abs(y_left - y_right)


does in no way return coordinates, it returns a distance. Also left and right was misleading me, I thought of the two finger positions. Also you claim the parameters are ints. Actually you pass characters. That is sloppy.

dist_a = get_coordinates(word_a, chars[index]) + get_dp(index + 1, chars[index], word_b)


is near to obfuscation. get_coordinates delivers a distance, word_a is not a word but a character where one finger is on, and what get_dp delivers cannot be guessed from the name nor is a docstring existing.

Algorithm

You use depth first search (DFS) while for finding the shortest path typically breadth first (BFS) is the better approach. With DFS you have to search the whole tree. By introducing an lru cache you found a nice trick to shortcut some branches. Still you cannot find the shortest path early but have to check the whole tree.

While the fingers are exchangeable you handle them as if they could not be swapped. So you find two optimal paths, one starting with the left finger, one starting with the right. Identical sequence, only the fingers are swapped. Also the cache does not match swapped fingers.

Cache

As already said, your cache does not match swapped fingers. By sorting the fingers you could match them. You do the lru cache on a function in a function. As the inner function is only existing while the outer is running also your cache is working for a single word only. Another call with the same word cannot be served from cache. If you pull the function on class level and change the signature to hold the remaining word instead of the index you could reuse cached "endgames".

A function that would greatly benefit from a lru cache is get_coordinates (read get_distance)

Hostile test cases

You should implement a BFS with priority queue. Then you do some logging and timing on tests like "FY"*150. While the minimum distance is 0, your DFS evaluates branches at a distance of near 2700. A BFS would register nodes at a max distance of 9 but would never follow them.

Other

The line

chars = ''.join(a for a, b in zip(word, word[1:] + ' ') if a != b)


would deserve an explanatory comment or a nice function name.