500. Keyboard Row

EasyArrayHash TableString

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 (where a 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 string s. 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 expression s[ord(c.lower()) - ord('a')] looks up the row for each character c. If all characters c in w return the same row value as the first letter (x), then all() 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 Evaluator

Example 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 letter h 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 that e, l, and o 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 letter a is also in the second row, and the next d 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 letters e, a, and c 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 list words.
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 list words.
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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know