Keyboard Row - Complete Solution Guide

Keyboard Row is LeetCode problem 500, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an array of strings words , return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below . Note that the strings are case-insensitive , both lowercased and uppercased of the same letter are treated as if they are at the same row. In the American keyboard : the first row consists of the characters "qwertyuiop" , the second row consists of the characters "asdfghjkl" , and the third row consists of the characters "zxcvbnm" . Exampl

Detailed Explanation

The problem asks us to identify words from a given list that can be typed using only one row of the American keyboard (qwertyuiop, asdfghjkl, zxcvbnm). The comparison should be case-insensitive, meaning 'A' and 'a' are considered the same. The input is an array of strings, and the output is a new array containing only the words that meet the single-row typing condition.

Solution Approach

The solution iterates through each word in the input list. For each word, it converts it to lowercase. Then, it iterates through the characters of the lowercase word, determining the row each character belongs to. The algorithm maintains a variable to store the initial row of the word and compares the row of subsequent characters with this initial row. If any character belongs to a different row, the algorithm marks the word as invalid. If all characters belong to the same row, the word is added to the result list.

Step-by-Step Algorithm

1. Step 1: Initialize an empty result list to store valid words.
2. Step 2: Iterate through each word in the input list.
3. Step 3: Convert the current word to lowercase.
4. Step 4: Initialize a 'row' variable (or similar) to track the keyboard row for the current word. Set a 'flag' variable to True to indicate that the word is initially valid.
5. Step 5: Iterate through each character in the lowercase word.
6. Step 6: Determine the row number (1, 2, or 3) the current character belongs to. If the character does not appear in any of keyboard rows, there is likely an error with how you define the keyboard rows. It's generally safe to assume the strings only contain characters that are on the keyboard.
7. Step 7: If 'row' is still empty (meaning this is the first character being checked), set 'row' to the row number of the current character. Also if `row` is empty for the C solutions, allocate memory for each new string that will be added to the return result.
8. Step 8: If 'row' is not empty, check if the row number of the current character is the same as the value of 'row'. If it is not, set 'flag' to False and break out of the inner loop.
9. Step 9: After iterating through all characters in the word, if 'flag' is still True, add the original (un-lowercased) word to the result list.
10. Step 10: After iterating through all words, return the result list.

Key Insights

• Insight 1: Case-insensitivity: Convert each word to lowercase to simplify the row checking process.
• Insight 2: Row Identification: Determine which row each character belongs to.
• Insight 3: Consistency Check: Verify that all characters in a word belong to the same row.

Complexity Analysis

Time Complexity: O(n*m)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, String.

Companies

Asked at: MathWorks.