Go Lang Programming Exercise: Single-Row Keyboard

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

Hints:
Can be the problem divided in parts, so solving each part and sum their solutions it should return the answer? Yes, you only need to divide the problem in finger jumps.
In each finger jump you need to move your finger from one character to another, you need to know its index.
Map each character to it’s index.
Use a hash table to do that.

GoLang Programming to Solve Single Row Keyboard

With GoLang, we need to take special care/handling when converting between float64 and int/int32. First we create a hash map using syntax make(map[byte]int) and remember the index for each keys.

Then, we accumulate the cost of distance between neighbouring keys. The cost is defined in type float64, and being truncated using math.Trunc last.

1
2
3
4
5
6
7
8
9
10
11

func calculateTime(keyboard string, word string) int {
    var keys = make(map[byte]int)
    for i:=0; i < len(keyboard); i ++ {
        keys[keyboard[i]] = i
    }
    var ans float64 = float64(keys[word[0]])
    for i:=1; i < len(word); i ++ {
        ans += math.Abs(float64(keys[word[i]] - keys[word[i-1]]))
    }
    return int(math.Trunc(ans))
}

func calculateTime(keyboard string, word string) int {
    var keys = make(map[byte]int)
    for i:=0; i < len(keyboard); i ++ {
        keys[keyboard[i]] = i
    }
    var ans float64 = float64(keys[word[0]])
    for i:=1; i < len(word); i ++ {
        ans += math.Abs(float64(keys[word[i]] - keys[word[i-1]]))
    }
    return int(math.Trunc(ans))
}

Single Row Keyboard Algorithms

• Go Lang Programming Exercise: Single-Row Keyboard
• Single-Row Keyboard Algorithms to Estimate the Finger Moving Time
• Teaching Kids Programming – Single-Row Keyboard via Hash Table

–EOF (The Ultimate Computing & Technology Blog) —