Skip to content

1165. Single-Row Keyboard πŸ”’

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 \(pos\) of length \(26\) to store the position of each character on the keyboard, where \(pos[c]\) represents the position of character \(c\) on the keyboard.

Then we traverse the string \(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 \(word\) is traversed.

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

The time complexity is \(O(n)\), and the space complexity is \(O(C)\). Here, \(n\) is the length of the string \(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