Burak Dede's Blog

Keyboard Row Problem - Leetcode

Problem

This is my approach to the solution of keyboard row problem from Leetcode. https://leetcode.com/problems/keyboard-row/description/

Basically we are trying to find if the word we are about to type can be typed with letters in one row of the keyboard. My naive approach is to store 3 hashsets and for each of the words we are checking with containsAll like methods check if all letters exist in any of the sets. If thats the case add it to list otherwise skip.

public String[] findWords(String[] words) {
    List<String> matches = new ArrayList<>();
    Character[] firstRow = {'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'};
    Set<Character> firstSet = new HashSet<>(Arrays.asList(firstRow));
    Character[] secondRow = {'A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L'};
    Set<Character> secondSet = new HashSet<>(Arrays.asList(secondRow));
    Character[] thirdRow = {'Z', 'X', 'C', 'V', 'B', 'N', 'M'};
    Set<Character> thirdSet = new HashSet<>(Arrays.asList(thirdRow));

    for(String word : words) {
        HashSet<Character> chars = new HashSet<>();
        for (Character c : word.toCharArray()) {
            chars.add(Character.toUpperCase(c));
        }

        if(firstSet.containsAll(chars) || secondSet.containsAll(chars) || thirdSet.containsAll(chars)) {
            matches.add(word);
        }
    }

    return matches.toArray(new String[] {});
}

This will lookup all the words, lets call words list length M and longest word N so we expect total time or O(M*N) and since key rows is fixed length space complexity would depend on the longest word and how unique it is.