# Java Easy To Understand Solution O(n)

• Explanation
We start off with assigning each alphabet character to a row, by defining sets row1, row2, row3. These sets will help us determine if any given character is found in a specific row for fast look-up in O(1) time. Additionally, we define variable map to help us determine which row each character should belong to - this will help us choose a row to search in.

For each word, we select the appropriate row# set based on map. Then, we scan through all of the word's characters to see if they belong in that row# set. If they do, we append it to our result; otherwise, we do not append.

Time Complexity
The time complexity could be argued to be O(n), where n is the total number of characters in our words array, since setupCharsInRows(...), which itself runs in constant time, made subsequent look-ups run in O(1).

``````class Solution {

public void setupCharsInRows(Set<Character> row1, Set<Character> row2,
Set<Character> row3, Map<Character, Integer> map) {
Character[] row1Array = {'q', 'w', 'e', 'r', 't', 'y', 'u', 'i',
'o', 'p'};
Character[] row2Array = {'a', 's', 'd', 'f', 'g', 'h', 'j', 'k',
'l'};
Character[] row3Array = {'z', 'x', 'c', 'v', 'b', 'n', 'm'};
// Add all our characters into sets for future fast look-up.
for (int i = 0; i < row1Array.length; i++) {
map.put(row1Array[i], 1);
}
for (int i = 0; i < row2Array.length; i++) {
map.put(row2Array[i], 2);
}
for (int i = 0; i < row3Array.length; i++) {
map.put(row3Array[i], 3);
}
}

public boolean isWordInRow(String word, Set<Character> row) {
for (int i = 0; i < word.length(); i++) {
char c = Character.toLowerCase(word.charAt(i));
if (!row.contains(c)) {
return false;
}
}
return true;
}

public String[] findWords(String[] words) {
List<String> result = new ArrayList<>();
Set<Character> row1 = new HashSet<>();
Set<Character> row2 = new HashSet<>();
Set<Character> row3 = new HashSet<>();
// Our map will indicate which row characters belong to
Map<Character, Integer> map = new HashMap<>();

// Setup row1, row2, row3, map with hard-coded logic.
setupCharsInRows(row1, row2, row3, map);

for (int i = 0; i < words.length; i++) {
String word = words[i];
// Our map indicates which row the character word[0] belongs to
int row = map.get(Character.toLowerCase(word.charAt(0)));
if (row == 1 && isWordInRow(word, row1) ||
row == 2 && isWordInRow(word, row2) ||
row == 3 && isWordInRow(word, row3)) {