Single-Row Keyboard — LeetCode 1165 Python Solution

The problem

There is a special keyboard with all keys in a single row. Given a string keyboard of length 26 indicating the layout of the keyboard (indexed from 0 to 25).

Example

Input

keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"

Output

4

Explanation

The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.

Python solution

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        pos = {c: i for i, c in enumerate(keyboard)}
        ans = i = 0
        for c in word:
            ans += abs(pos[c] - i)
            i = pos[c]
        return ans

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1165. Single-Row Keyboard is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems