1165. Single-Row Keyboard 🔒

SourceBiweekly Contest 7 Q1DifficultyEasyRating1199

Description

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 <= 104
• word[i] is an English lowercase letter.

Solutions

Solution 1: Hash Table or Array

We can use a hash table or an array \(\textit{pos}\) of length \(26\) to store the position of each character on the keyboard, where \(\textit{pos}[c]\) represents the position of character \(c\) on the keyboard.

Then we traverse the string \(\textit{word}\), using a variable \(i\) to record the current position of the finger, initially \(i = 0\). Each time, we calculate the position \(j\) of the current character \(c\) on the keyboard, and increase the answer by \(|i - j|\), then update \(i\) to \(j\). Continue to traverse the next character until the entire string \(\textit{word}\) is traversed.

After traversing the string \(\textit{word}\), we can get the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(C)\), where \(n\) is the length of the string \(\textit{word}\), and \(C\) is the size of the character set. In this problem, \(C = 26\).

1
2
3
4
5
6
7
8

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

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

class Solution {
    public int calculateTime(String keyboard, String word) {
        int[] pos = new int[26];
        for (int i = 0; i < 26; ++i) {
            pos[keyboard.charAt(i) - 'a'] = i;
        }
        int ans = 0, i = 0;
        for (int k = 0; k < word.length(); ++k) {
            int j = pos[word.charAt(k) - 'a'];
            ans += Math.abs(i - j);
            i = j;
        }
        return ans;
    }
}

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

class Solution {
public:
    int calculateTime(string keyboard, string word) {
        int pos[26];
        for (int i = 0; i < 26; ++i) {
            pos[keyboard[i] - 'a'] = i;
        }
        int ans = 0, i = 0;
        for (char& c : word) {
            int j = pos[c - 'a'];
            ans += abs(i - j);
            i = j;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func calculateTime(keyboard string, word string) (ans int) {
    pos := [26]int{}
    for i, c := range keyboard {
        pos[c-'a'] = i
    }
    i := 0
    for _, c := range word {
        j := pos[c-'a']
        ans += abs(i - j)
        i = j
    }
    return
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

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

function calculateTime(keyboard: string, word: string): number {
    const pos: number[] = Array(26).fill(0);
    for (let i = 0; i < 26; ++i) {
        pos[keyboard.charCodeAt(i) - 97] = i;
    }
    let ans = 0;
    let i = 0;
    for (const c of word) {
        const j = pos[c.charCodeAt(0) - 97];
        ans += Math.abs(i - j);
        i = j;
    }
    return ans;
}

Comments