Question

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$.

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

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;
  }
}

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;
  }
};

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
}

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;
}