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|.
Return the total time to type the string word.
Example 1:
Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba" Output: 4 Explanation: The index moves from 0 to 2 to write 'c' then from 2 to 1 to write 'b' then from 1 to 0 to write 'a'. Total time = 2 + 1 + 1 = 4.
Example 2:
Input: keyboard = "pqrstuvwxyzabcdefghijklmno", word = "leetcode" Output: 73
Constraints:
keyboard.length == 26keyboard contains each English lowercase letter exactly once in some order.1 <= word.length <= 104word contains English lowercase letters only.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach to this keyboard problem involves trying every possible character-by-character path to spell out the target word. We essentially simulate using the keyboard in every conceivable way to find the fastest way to type the word. We then choose the fastest one.
Here's how the algorithm would work step-by-step:
def single_row_keyboard_brute_force(keyboard, word):
keyboard_length = len(keyboard)
word_length = len(word)
minimum_distance = float('inf')
def calculate_distance(current_index, word_index, current_distance):
nonlocal minimum_distance
# If we've reached the end of the word, update the minimum distance
if word_index == word_length:
minimum_distance = min(minimum_distance, current_distance)
return
target_character = word[word_index]
# Find the index of the target character on the keyboard
target_index = keyboard.find(target_character)
distance = abs(current_index - target_index)
# Recursively calculate the distance for the next character in the word
calculate_distance(target_index, word_index + 1, current_distance + distance)
# The starting position is always index 0 on the keyboard
calculate_distance(0, 0, 0)
return minimum_distanceThe goal is to find the total distance a finger needs to travel on a single-row keyboard to type a given word. The key is to quickly figure out where each letter is located on the keyboard and then calculate the distance between each consecutive letter.
Here's how the algorithm would work step-by-step:
def calculate_keyboard_distance(keyboard_layout, word_to_type):
keyboard_position_map = {}
for index, character in enumerate(keyboard_layout):
keyboard_position_map[character] = index
total_distance_traveled = 0
# Initialize the starting position to the first character in the word
current_position = keyboard_position_map[word_to_type[0]]
# Iterate through the rest of the word to calculate distance
for i in range(1, len(word_to_type)):
next_character = word_to_type[i]
next_position = keyboard_position_map[next_character]
# Calculate the absolute distance between positions
distance = abs(next_position - current_position)
total_distance_traveled += distance
# Update the current position for the next iteration
current_position = next_position
return total_distance_traveled| Case | How to Handle |
|---|---|
| Empty keyboard string | Return 0 immediately since no characters can be found. |
| Null keyboard or word string | Throw IllegalArgumentException to signal invalid input. |
| Keyboard string length 1 | If the target word has length 1, return 0, else return Integer.MAX_VALUE or throw an exception, based on problem requirement. |
| Word string contains characters not in keyboard | Handle missing characters by returning Integer.MAX_VALUE when character location is missing in the map. |
| Word string is very long (potential performance issue) | HashMap lookup provides O(1) access, making time complexity linearly proportional to the word's length. |
| Keyboard string contains duplicate characters. | The last occurrence of duplicate characters in keyboard overwrites the previous index in hashmap, using the correct character index. |
| Word string is empty | Return 0 since no movement is required. |
| Integer overflow if the word is extremely long, and characters are far apart in keyboard layout | Use long to store the distance to prevent integer overflow, and cast back to int if needed and appropriate, handling the overflow if the distance exceeds Integer.MAX_VALUE. |