Welcome to Subscribe On Youtube
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 == 26keyboardcontains each English lowercase letter exactly once in some order.1 <= word.length <= 104word[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 { 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; } }; -
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 -
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; }