Java 4 ms solution using HashSet


  • 3
    I
    public class Solution {
        public String[] findWords(String[] words) {
            Set<Character> row1 = new HashSet<>();
            Set<Character> row2 = new HashSet<>();
            Set<Character> row3 = new HashSet<>();
            
            row1.add('q');
            row1.add('w');
            row1.add('e');
            row1.add('r');
            row1.add('t');
            row1.add('y');
            row1.add('u');
            row1.add('i');
            row1.add('o');
            row1.add('p');
            
            row2.add('a');
            row2.add('s');
            row2.add('d');
            row2.add('f');
            row2.add('g');
            row2.add('h');
            row2.add('j');
            row2.add('k');
            row2.add('l');
            
            row3.add('z');
            row3.add('x');
            row3.add('c');
            row3.add('v');
            row3.add('b');
            row3.add('n');
            row3.add('m');
            
            List<String> result = new ArrayList<>();
            
            for(String word : words)
            {
                char[] charArray = word.toLowerCase().toCharArray();
            
                int lenOfWord = charArray.length;
                
                int count = 0;
                
                for(Character ch : charArray)
                {
                    if(row1.contains(ch))
                        count++;
                   else 
                       break;
    
                }
                
                if(count == lenOfWord)
                {
                    result.add(word);
                    continue;
                }
                
                count = 0;
                
                for(Character ch : charArray)
                {
                    if(row2.contains(ch))
                        count++;
                   else 
                       break;
                }
                
                if(count == lenOfWord)
                {
                    result.add(word);
                    continue;
                }
                
                count = 0;
                
                for(Character ch : charArray)
                {
                    if(row3.contains(ch))
                        count++;
                   else 
                       break;
                }
                
                if(count == lenOfWord)
                {
                    result.add(word);
                }
            }
            return result.toArray(new String[result.size()]);
        }
    }
    

    Used 3 hashsets for 3 rows in the keyboard and verified each character in each word of the array with hashset.

    Open to suggestions and constructive criticism. Thanks !!


  • 0
    M

    why don't you just create a string which contains "qwertyuiop" but using Set?


  • 1
    I

    @ming54 HashSet has add() and contains() time complexity of O(1). It has minor effect in this case but, String.contains() takes O(n) time.


  • 0
    M

    @indish Thanks for the explanation!
    But I write a contain method which is also O(n), but the total time my code consume is also 4ms.
    Could you have a look at my code and tell me the complexity? Thank you!
    I only know that of a for loop is O(n) but nothing else. also space consumption.
    https://discuss.leetcode.com/topic/79006/4ms-no-map-naive-solution-in-java-with-explanation


  • 0
    I

    @ming54 Its not a big problem in this context because the number of alphabets won't change for keyboard. When the size varies it makes a difference.


  • 0
    L

    I tried almost similar logic but instead of using a counter. I tried with hashset containsAll method. It is not working. Any idea why?

    for (int i=0;i<words.length;i++)
    {
    if((a.containsAll(Arrays.asList(words[i].toLowerCase().toCharArray())) || b.containsAll(Arrays.asList(words[i].toLowerCase().toCharArray()))) || c.containsAll(Arrays.asList(words[i].toLowerCase().toCharArray())) )
    {

             list.add(words[i]);
         }
     }

  • 0
    I

    @LeetPanda Go through this. When you called Arrays.asList it created a list with single char[] i.e. you created a List<char[]> but you need List<Character> to compare it with. So, it failed to compare.
    http://stackoverflow.com/questions/15664396/java-containsall-does-not-return-true-when-given-lists


  • 0
    W

    @indish said in Java 4 ms solution using HashSet:

    public class Solution {
        public String[] findWords(String[] words) {
            Set<Character> row1 = new HashSet<>();
            Set<Character> row2 = new HashSet<>();
            Set<Character> row3 = new HashSet<>();
            
            row1.add('q');
            row1.add('w');
            row1.add('e');
            row1.add('r');
            row1.add('t');
            row1.add('y');
            row1.add('u');
            row1.add('i');
            row1.add('o');
            row1.add('p');
            
            row2.add('a');
            row2.add('s');
            row2.add('d');
            row2.add('f');
            row2.add('g');
            row2.add('h');
            row2.add('j');
            row2.add('k');
            row2.add('l');
            
            row3.add('z');
            row3.add('x');
            row3.add('c');
            row3.add('v');
            row3.add('b');
            row3.add('n');
            row3.add('m');
            
            List<String> result = new ArrayList<>();
            
            for(String word : words)
            {
                char[] charArray = word.toLowerCase().toCharArray();
            
                int lenOfWord = charArray.length;
                
                int count = 0;
                
                for(Character ch : charArray)
                {
                    if(row1.contains(ch))
                        count++;
                   else 
                       break;
    
                }
                
                if(count == lenOfWord)
                {
                    result.add(word);
                    continue;
                }
                
                count = 0;
                
                for(Character ch : charArray)
                {
                    if(row2.contains(ch))
                        count++;
                   else 
                       break;
                }
                
                if(count == lenOfWord)
                {
                    result.add(word);
                    continue;
                }
                
                count = 0;
                
                for(Character ch : charArray)
                {
                    if(row3.contains(ch))
                        count++;
                   else 
                       break;
                }
                
                if(count == lenOfWord)
                {
                    result.add(word);
                }
            }
            return result.toArray(new String[result.size()]);
        }
    }
    

    Used 3 hashsets for 3 rows in the keyboard and verified each character in each word of the array with hashset.

    Open to suggestions and constructive criticism. Thanks !!


Log in to reply
 

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