Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1165.html

1165. Single-Row Keyboard

Level

Easy

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

Solution

Initially the index is 0. For each letter in word, find out the index of the letter in keyboard, calculate the time taken to move the finger, and add the time taken to the total time. Finally, return the total time.

  • class Solution {
        public int calculateTime(String keyboard, String word) {
            int time = 0;
            int index = 0;
            int length = word.length();
            for (int i = 0; i < length; i++) {
                char c = word.charAt(i);
                int curIndex = keyboard.indexOf(c);
                time += Math.abs(curIndex - index);
                index = curIndex;
            }
            return time;
        }
    }
    
  • // OJ: https://leetcode.com/problems/single-row-keyboard/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int calculateTime(string keyboard, string word) {
            unordered_map<char, int> m;
            for (int i = 0; i < 26; ++i) m[keyboard[i]] = i;
            int prev = 0, ans = 0;
            for (char c : word) {
                int i = m[c];
                ans += abs(prev - i);
                prev = i;
            }
            return ans;
        }
    };
    
  • class Solution:
        def calculateTime(self, keyboard: str, word: str) -> int:
            index = {c: i for i, c in enumerate(keyboard)}
            res = t = 0
            for c in word:
                res += abs(index[c] - t)
                t = index[c]
            return res
    
    
    
  • func calculateTime(keyboard string, word string) int {
    	index := map[byte]int{}
    	for i := 0; i < len(keyboard); i++ {
    		index[keyboard[i]] = i
    	}
    	res := 0
    	t := 0
    	for i := 0; i < len(word); i++ {
    		res += abs(index[word[i]] - t)
    		t = index[word[i]]
    	}
    	return res
    }
    
    func abs(x int) int {
    	if x < 0 {
    		return -x
    	}
    	return x
    }
    

All Problems

All Solutions