algoadvance

Leetcode 500. Keyboard Row

Problem Statement

Leetcode problem 500, “Keyboard Row”, asks you to determine if a given word can be typed using letters from only one row of a keyboard. The common QWERTY keyboard layout has the following rows:

1. “QWERTYUIOP” (or “qwertyuiop”)
2. “ASDFGHJKL” (or “asdfghjkl”)
3. “ZXCVBNM” (or “zxcvbnm”)

You are given a list of words, and you need to return the words that can be typed using letters from only one row of this keyboard.

Clarifying Questions

1. Case Sensitivity: Should the function handle both upper and lower case letters?
   • Yes, the function should handle both upper and lower case letters.
2. Input Constraints: Are there any constraints on the length or number of words?
   • Typical constraints: 1 <= words.length <= 20, and each word length is 1 <= word.length <= 100, only containing letters.
3. Output Format: What should the output be?
   • The output should be a list of words that can be typed using letters from only one keyboard row.

Strategy

1. Map Rows to Sets: Create a mapping of the rows to sets containing their respective letters for quick lookup.
2. Check Each Word: For each word, determine the set of rows it can belong to:
   • If all characters of the word belong to one of these sets, add the word to the result.
3. Use Lowercase For Comparison: Convert each character to lowercase to simplify checks.

Code

Here’s the C++ implementation:

#include <vector>
#include <string>
#include <unordered_set>
#include <cctype>

using namespace std;

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        unordered_set<char> row1 = {'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'};
        unordered_set<char> row2 = {'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'};
        unordered_set<char> row3 = {'z', 'x', 'c', 'v', 'b', 'n', 'm'};
        
        vector<string> result;
        
        for (const string& word : words) {
            if (isValid(word, row1) || isValid(word, row2) || isValid(word, row3)) {
                result.push_back(word);
            }
        }
        
        return result;
    }
    
private:
    bool isValid(const string& word, const unordered_set<char>& row) {
        for (char c : word) {
            if (row.find(tolower(c)) == row.end()) {
                return false;
            }
        }
        return true;
    }
};

Time Complexity

• Initialization: Creating the sets for rows takes constant time, O(1).
• Processing Each Word:
  • For each word, checking if all characters belong to a single row takes O(m) where m is the length of the word.
  • Since checking each character involves set lookup, which is O(1), the overall complexity for a word is O(m).

Given n words and assuming the average length of a word is m:

• Total Time Complexity: O(n * m)

This is efficient given the constraints of the problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?