Leetcode 0500. Keyboard Row

Given an array of strings `words`, 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"`.　

Easy

Description

Given an array of strings words, 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", and
• the third row consists of the characters "zxcvbnm".

Example 1:

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

Example 2:

Input: words = ["omk"]
Output: []

Example 3:

Input: words = ["adsdf","sfd"]
Output: ["adsdf","sfd"]

Constraints:

• 1 <= words.length <= 20
• 1 <= words[i].length <= 100
• words[i] consists of English letters (both lowercase and uppercase).

Solution

class Solution {
    /**
     * Iteration
     * Time Complexity: BigO(N^2)
     * Space Complexity: BigO(1)
     */
    public String[] findWords(String[] words) {
        HashSet<String> row1 = new HashSet<>(
            Arrays.asList("q", "w", "e", "r", "t", "y", "u", "i", "o", "p")
          );
        HashSet<String> row2 = new HashSet<>(
            Arrays.asList("a","s","d","f","g","h","j","k","l")
          );
        HashSet<String> row3 = new HashSet<>(
            Arrays.asList("z","x","c","v","b","n","m")
          );

        List<String> ans = new ArrayList<>();

        for(String w: words) {
            String word = w.toLowerCase();
            if(row1.contains(word.substring(0, 1))) {
                if(valid(row1, word)) {
                    ans.add(w);
                }
            } else if(row2.contains(word.substring(0, 1))) {
                if(valid(row2, word)) {
                    ans.add(w);
                }
            } else {
                if(valid(row3, word)) {
                    ans.add(w);
                }
            }
        }
        return ans.toArray(new String[0]);
    }

    private boolean valid(HashSet<String> dict, String word) {
        boolean valid = true;
        for(int i = 0; i < word.length(); i++) {
            String ch = word.substring(i, i + 1);
            if(!dict.contains(ch)) {
                valid = false;
            }
        }
        return valid;
    }
}