algoadvance

Leetcode 500. Keyboard Row

Problem Statement

Given an array of strings, return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below.

In the American keyboard:

• The first row consists of the characters "qwertyuiop".
• The second row consists of the characters "asdfghjkl".
• The third row consists of the characters "zxcvbnm".

Example:

Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Note:

1. You may use one character in the string more than once.
2. You may assume the input string will only contain letters of the alphabet.

Clarifying Questions

1. Should the solution be case-insensitive?
   • Yes, words should be evaluated case-insensitively.
2. Is the input guaranteed to be non-null and contain only alphabetic characters?
   • Yes, you can assume the input is non-null and contains only alphabetic characters.
3. Is the output required to be in the same order as the input?
   • Yes, the output should maintain the same order as the words in the input.

Strategy

1. Create sets for each row of the keyboard for easy lookup.
2. Convert each word to lowercase to handle case insensitivity.
3. For each word in the input array, check if all characters in the word belong to one of the row sets.
4. If they do, add the word to the result list.
5. Return the result list.

Code

import java.util.*;

public class Solution {
    public String[] findWords(String[] words) {
        // Define the sets for each keyboard row
        Set<Character> row1 = new HashSet<>(Arrays.asList(
                'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'));
        Set<Character> row2 = new HashSet<>(Arrays.asList(
                'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'));
        Set<Character> row3 = new HashSet<>(Arrays.asList(
                'z', 'x', 'c', 'v', 'b', 'n', 'm'));

        List<String> result = new ArrayList<>();
        
        for (String word : words) {
            if (canBeTypedWithOneRow(word.toLowerCase(), row1) || 
                canBeTypedWithOneRow(word.toLowerCase(), row2) || 
                canBeTypedWithOneRow(word.toLowerCase(), row3)) {
                result.add(word);
            }
        }
        
        return result.toArray(new String[0]);
    }

    private boolean canBeTypedWithOneRow(String word, Set<Character> row) {
        for (char c : word.toCharArray()) {
            if (!row.contains(c)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] input = {"Hello", "Alaska", "Dad", "Peace"};
        String[] output = solution.findWords(input);
        System.out.println(Arrays.toString(output)); // Should print ["Alaska", "Dad"]
    }
}

Time Complexity

• Checking if a character belongs to a set takes O(1) because sets have average O(1) time complexity for lookups.
• Converting each word to lowercase takes O(m), where m is the length of the word.
• The time complexity for iterating through each word and checking membership in one of the row sets is:
  • O(m) for converting the word to lowercase,
  • O(n) for iterating over the characters in the word,
• Thus, for n words of maximum length m:
  • The overall time complexity is O(n * m).

Therefore, the solution is efficient and should work well within typical input size constraints.

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?