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.
Note that the strings are case-insensitive, both lowercased and uppercased of the same letter are treated as if they are at the same row.
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"]
Explanation:
Both "a" and "A" are in the 2nd row of the American keyboard due to case insensitivity.
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).
My Solution
We can first initialize 3 HashSets with the characters in each row. Then we iterate each word in the words array and check that all the characters are in one and only one HashSet. We also have to make sure to convert every character to lowercase. If it is, we add the String to our output list. Finally once we have iterated all the words in the words array, we create our output array and transfer all the words in our output list to our output array.
Time complexity is O(m*n), where m is the number of Strings in words and n is the length of the longest String in n, because we iterate through every character in every word of the words array. Space Complexity is also O(m*n) because of the space required for the output array.
class Solution {
public String[] findWords(String[] words) {
List<String> out = new ArrayList<>();
Set<Character> first = new HashSet<>();
Set<Character> second = new HashSet<>();
Set<Character> third = new HashSet<>();
int n = words.length;
String first_str = "qwertyuiop";
String second_str = "asdfghjkl";
String third_str = "zxcvbnm";
for (char c : first_str.toCharArray()) {
first.add(c);
}
for (char c : second_str.toCharArray()) {
second.add(c);
}
for (char c : third_str.toCharArray()) {
third.add(c);
}
for (String s : words) {
char c = Character.toLowerCase(s.charAt(0));
int set = 0;
boolean found = true;
if (first.contains(c)) {
set = 1;
}
else if (second.contains(c)) {
set = 2;
}
else {
set = 3;
}
for (char d : s.toCharArray()) {
d = Character.toLowerCase(d);
if ((!first.contains(d) && set == 1) ||
(!second.contains(d) && set == 2) ||
(!third.contains(d) && set == 3)) {
found = false;
break;
}
}
if (found) {
out.add(s);
}
}
String[] out_arr = new String[out.size()];
for (int i = 0; i < out.size(); i++) {
out_arr[i] = out.get(i);
}
return out_arr;
}
}