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), initially your finger is at index 0. To type a character, you have to move your finger to the index of the desired character. The time taken to move your finger from index i to index j is |i – j|. You want to type a string word. Write a function to calculate how much time it takes to type it with one finger.

Example 1:
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’.
Total time = 2 + 1 + 1 = 4.

Example 2:
Input: keyboard = “pqrstuvwxyzabcdefghijklmno”, word = “leetcode”
Output: 73

Constraints:

• keyboard.length == 26
• keyboard contains each English lowercase letter exactly once in some order.
• 1 <= word.length <= 10^4
• word[i] is an English lowercase letter.

Using Hash Map to Record the Key Indices

We can use a hash map to record the position/index of the keys. Then, we can iterate the word, simulating the fingers moving character by character, adding up the total time required.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int calculateTime(string keyboard, string word) {
        unordered_map<char, int> data;
        for (int i = 0; i < keyboard.size(); ++ i) {
            data[keyboard[i]] = i;
        }
        int r = data[word[0]];
        for (int i = 1; i < word.size(); ++ i) {
            r += abs(data[word[i]] - data[word[i - 1]]);
        }
        return r;
    }
};

class Solution {
public:
    int calculateTime(string keyboard, string word) {
        unordered_map<char, int> data;
        for (int i = 0; i < keyboard.size(); ++ i) {
            data[keyboard[i]] = i;
        }
        int r = data[word[0]];
        for (int i = 1; i < word.size(); ++ i) {
            r += abs(data[word[i]] - data[word[i - 1]]);
        }
        return r;
    }
};

Using a static counter array

As the input keyboard has exactly 26 characters, we can use O(1) static counter array that is of size 26.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int calculateTime(string keyboard, string word) {
        int data[26];
        for (int i = 0; i < keyboard.size(); ++ i) {
            data[keyboard[i] - 97] = i;
        }
        int r = data[word[0] - 97];
        for (int i = 1; i < word.size(); ++ i) {
            r += abs(data[word[i] - 97] - data[word[i - 1] - 97]);
        }
        return r;
    }
};

class Solution {
public:
    int calculateTime(string keyboard, string word) {
        int data[26];
        for (int i = 0; i < keyboard.size(); ++ i) {
            data[keyboard[i] - 97] = i;
        }
        int r = data[word[0] - 97];
        for (int i = 1; i < word.size(); ++ i) {
            r += abs(data[word[i] - 97] - data[word[i - 1] - 97]);
        }
        return r;
    }
};

Both implementations run at O(N) time where N is the length of the word.

Python Implementation of Single-Row Keyboard Algorithm

In Python, we can use the enumerate function to record the index, and we can then accumulate the costs by iterating the keys. A previous distance to type the key (initialised to zero) is remembered.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        d = {}
        for x, y in enumerate(keyboard):
            d[y] = x  # remember the index for each keys.
        ans = 0
        prev = 0
        for i in word:
            ans += abs(d[i] - prev)
            prev = d[i]
        return ans

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        d = {}
        for x, y in enumerate(keyboard):
            d[y] = x  # remember the index for each keys.
        ans = 0
        prev = 0
        for i in word:
            ans += abs(d[i] - prev)
            prev = d[i]
        return ans

–EOF (The Ultimate Computing & Technology Blog) —