Java Easy To Understand Solution O(n)


  • 0
    B

    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++) {
                row1.add(row1Array[i]);
                map.put(row1Array[i], 1);
            }
            for (int i = 0; i < row2Array.length; i++) {
                row2.add(row2Array[i]);
                map.put(row2Array[i], 2);
            }
            for (int i = 0; i < row3Array.length; i++) {
                row3.add(row3Array[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)) {
                    result.add(word);
                }
            }      
            String[] res = new String[result.size()];      
            return result.toArray(res);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.