500. Keyboard Row
Problem Description
In this problem, we are given an array of strings named words
. Our task is to identify which of these words can be typed using letters from only one row on an American keyboard. The American keyboard has three rows of letters:
- The first row contains the letters "qwertyuiop".
- The second row contains the letters "asdfghjkl".
- The third row contains the letters "zxcvbnm".
A word qualifies if all of its letters are found in one of these rows. The goal is to return a list of words that meet this criterion.
Intuition
To solve this problem, we create a mapping that tells us which row each letter of the alphabet belongs to. We then iterate over each word in the given words
array and for each word, we check if all its letters come from the same row.
To facilitate the row checking process, we create a string s
where the position of each character corresponds to a letter of the alphabet and its value represents the row number on the keyboard ('1' for the first row, '2' for the second row, and so on). This allows us to quickly check the row of a letter by computing its relative position in the alphabet ('a' as index 0, 'b' as index 1, etc.)
For instance, s[0]
would give us the row number for the letter 'a', which is '1'.
For each word, we start by looking up the row of its first letter. Then we use a simple loop (or a comprehension in Python) to check if every subsequent letter in the word is from the same row. If they all match the row of the first letter, we add the word to the answer list ans
. After we've checked all words, we return the list ans
of words that can be typed using only one row of the keyboard.
This solution is efficient because it checks each word against a constant string and avoids any complex data structures or operations.
Solution Approach
The solution uses a fairly straightforward algorithm that involves string manipulation and iteration. Here's a walkthrough of the implementation step by step:
-
Prepare the Keyboard Mapping: The string
s
"12210111011122000010020202"
is crafted such that the position of each character corresponds to a letter in the alphabet (wherea
is at index 0), and its value ('1', '2', or '3') indicates which row that letter is on the keyboard. It's a clever encoding because it enables quick access without the need for a more complex data structure like a dictionary. -
Iterate Over Each Word: The main loop of the function goes through each word in the given
words
list. -
Normalize the Case: Since the keyboard rows are case-insensitive, each letter of the word is converted to lowercase using
.lower()
. -
Find Row of the First Letter: For each word, the row of the first letter is determined using
ord(w[0].lower()) - ord('a')
to find the index in our mapping strings
.ord
is a built-in function that returns an integer representing the Unicode code point of the character. Thus,ord('a')
would be the base Unicode code point for lowercase letters. -
Check Consistency of Rows: We use a generator expression within the
all()
function to check if all characters in the current word belong to the same row. The expressions[ord(c.lower()) - ord('a')]
looks up the row for each characterc
. If all charactersc
inw
return the same row value as the first letter (x
), thenall()
returns True, and the word is consistent with just one keyboard row. -
Store the Valid Word: If the condition from step 5 is met, the word is appended to the answer list
ans
. -
Return Results: After all words have been checked, the final list
ans
contains only the words that can be typed using letters from one row of the keyboard and is returned.
This approach cleverly avoids nested loops and does not require extra space for a more complicated data structure, making the code concise and efficient.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example where our input array of words
is ["Hello", "Alaska", "Dad", "Peace"]
. We need to determine which of these words can be typed using letters from only one row on an American keyboard.
-
Prepare the Keyboard Mapping: We have the string
s = "12210111011122000010020202"
, which represents the row numbers of each letter in the alphabet. -
Iterate Over Each Word: We begin by examining each word in the array:
"Hello"
,"Alaska"
,"Dad"
, and"Peace"
. -
Normalize the Case: We convert each word to lowercase. The words are now
["hello", "alaska", "dad", "peace"]
. This step ensures comparison is case-insensitive. -
Find Row of the First Letter: Starting with
"hello"
, we find that the first letterh
is in the second row using the mapping (i.e.,s[ord('h') - ord('a')]
gives us '2'). -
Check Consistency of Rows: We then check each subsequent letter of
"hello"
. We find thate
,l
, ando
are not all in the second row. Therefore,"Hello"
does not qualify. -
Moving to "Alaska": Following the same processing, we determine that the first letter
a
is in the second row and all subsequent letters of"Alaska"
(l
,a
,s
,k
,a
) are also in the second row. This means that"Alaska"
qualifies. -
Processing "Dad": The first letter
d
is in the second row, but the second lettera
is also in the second row, and the nextd
is in the second row too. Thus,"Dad"
qualifies as well. -
Last Word "Peace": We see that the first letter
p
is in the first row. However, the next letterse
,a
, andc
are not on the first row. Therefore,"Peace"
does not qualify. -
Store the Valid Words: We have found that the words
"Alaska"
and"Dad"
both meet the criteria. -
Return Results: We return the list
["Alaska", "Dad"]
, as these are the words from the original input that can be typed using letters from only one row on the keyboard.
Solution Implementation
1class Solution:
2 def findWords(self, words: List[str]) -> List[str]:
3 # Initialize an empty list to store the valid words.
4 valid_words = []
5
6 # Mapping for each letter to its corresponding row on the keyboard.
7 row_mapping = "12210111011122000010020202"
8
9 # Iterate over each word in the provided list.
10 for word in words:
11 # Get the row for the first character of the word (convert to lowercase for uniformity).
12 first_char_row = row_mapping[ord(word[0].lower()) - ord('a')]
13
14 # Check if all characters in the word are in the same row as the first one.
15 if all(row_mapping[ord(char.lower()) - ord('a')] == first_char_row for char in word):
16 # If they are, append the word to our list of valid words.
17 valid_words.append(word)
18
19 # Return the list of valid words that can be typed using letters of one row on the keyboard.
20 return valid_words
21
1class Solution {
2
3 // Function to find the words that can be typed using letters of one row on the keyboard
4 public String[] findWords(String[] words) {
5 // String representing rows of the keyboard as numbers (1st row, 2nd row, 3rd row)
6 // a, b, c, etc. are mapped to their respective row numbers
7 String rowMapping = "12210111011122000010020202";
8 // List to store the eligible words
9 List<String> result = new ArrayList<>();
10
11 // Iterate over the array of words
12 for (String word : words) {
13 // Convert the word to lower case to make it case-insensitive
14 String lowerCaseWord = word.toLowerCase();
15 // Get the row number of the first character
16 char initialRow = rowMapping.charAt(lowerCaseWord.charAt(0) - 'a');
17 // Flag to check if all letters are in the same row
18 boolean canBeTyped = true;
19
20 // Iterate over characters of the word
21 for (char character : lowerCaseWord.toCharArray()) {
22 // Check if character is in a different row
23 if (rowMapping.charAt(character - 'a') != initialRow) {
24 canBeTyped = false;
25 break; // No need to check further if one letter is in a different row
26 }
27 }
28
29 // If all characters are in the same row, add the original word to the result
30 if (canBeTyped) {
31 result.add(word);
32 }
33 }
34
35 // Return the result as an array of strings
36 return result.toArray(new String[0]);
37 }
38}
39
1#include <vector>
2#include <string>
3#include <cctype> // Necessary for tolower function
4
5class Solution {
6public:
7 // Function to find the words that can be typed using letters of one row on the keyboard
8 vector<string> findWords(vector<string>& words) {
9
10 // Map each alphabet to a number corresponding to the row in the keyboard.
11 // 1 for first row, 2 for second row and so on.
12 string rowIndices = "12210111011122000010020202";
13 vector<string> filteredWords; // Resultant vector of words
14
15 // Iterate over each word in the input list
16 for (auto& word : words) {
17 bool canBeTyped = true; // flag to check if the word belongs to a single row
18 // Get the row for the first character of the word
19 char initialRow = rowIndices[tolower(word[0]) - 'a'];
20
21 // Iterate over each character in the word
22 for (char& character : word) {
23 // If the character does not belong to the same row as the first character, set flag to false
24 if (rowIndices[tolower(character) - 'a'] != initialRow) {
25 canBeTyped = false;
26 break; // Break out of the character loop since one mismatch is enough
27 }
28 }
29
30 // If the word can be typed using letters of one row, add it to the result
31 if (canBeTyped) {
32 filteredWords.emplace_back(word);
33 }
34 }
35
36 // Return the filtered list of words
37 return filteredWords;
38 }
39};
40
1// Function to find and return words that can be typed using letters of one row on a keyboard
2function findWords(words: string[]): string[] {
3 // The keyboard rows mapped to numbers '1' for the first row, '2' for the second, etc.
4 const keyboardRowMapping = '12210111011122000010020202';
5 // Initialize an array to store the valid words
6 const validWords: string[] = [];
7
8 // Iterate over each word provided in the input array
9 for (const word of words) {
10 // Convert the word to lowercase for uniform comparison
11 const lowerCaseWord = word.toLowerCase();
12 // Determine the keyboard row of the first character of the word
13 const baseRow = keyboardRowMapping[lowerCaseWord.charCodeAt(0) - 'a'.charCodeAt(0)];
14 // Assume the word is valid initially
15 let isWordValid = true;
16
17 // Check each character in the word to see if they are from the same keyboard row
18 for (const char of lowerCaseWord) {
19 if (keyboardRowMapping[char.charCodeAt(0) - 'a'.charCodeAt(0)] !== baseRow) {
20 // If the character is from a different row, mark the word as invalid and break out of the loop
21 isWordValid = false;
22 break;
23 }
24 }
25
26 // If the word is valid (all characters are from the same row), add it to the validWords array
27 if (isWordValid) {
28 validWords.push(word);
29 }
30 }
31
32 // Return the list of valid words
33 return validWords;
34}
35
Time and Space Complexity
The given Python function findWords
filters a list of words, selecting only those that can be typed using letters from the same row on a QWERTY keyboard.
Time Complexity:
The time complexity of the function can be considered as O(N * M)
where:
N
is the number of words in the input listwords
.M
is the average length of the words.
For each word, the function checks if all characters belong to the same row by referencing a pre-computed string s
that maps keyboard rows to characters. The comparison s[ord(c.lower()) - ord('a')] == x
runs in O(1)
time since it's a simple constant-time index access and comparison.
Therefore, we need to perform M
constant-time operations for each of the N
words, which leads to an overall time complexity of O(N * M)
.
Space Complexity:
The space complexity is O(N * K)
where:
N
is the number of words in the input listwords
.K
is the average space taken by each word.
The space complexity owes to the storage of the output list ans
. Each word that meets the condition is appended to ans
. In the worst case, all N
words meet the condition, and we end up storing all of them in ans
, hence the O(N * K)
space complexity.
The string s
used for row mapping is constant and does not scale with the input, so it does not add to the space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.