Short Easy Java with Explanation


  • 38
    public class Solution {
        public String[] findWords(String[] words) {
            String[] strs = {"QWERTYUIOP","ASDFGHJKL","ZXCVBNM"};
            Map<Character, Integer> map = new HashMap<>();
            for(int i = 0; i<strs.length; i++){
                for(char c: strs[i].toCharArray()){
                    map.put(c, i);//put <char, rowIndex> pair into the map
                }
            }
            List<String> res = new LinkedList<>();
            for(String w: words){
                if(w.equals("")) continue;
                int index = map.get(w.toUpperCase().charAt(0));
                for(char c: w.toUpperCase().toCharArray()){
                    if(map.get(c)!=index){
                        index = -1; //don't need a boolean flag. 
                        break;
                    }
                }
                if(index!=-1) res.add(w);//if index != -1, this is a valid string
            }
            return res.toArray(new String[0]);
        }
    }
    

  • 2

    same idea here, but just using int array for character hash and checking each row for a match one at a time simplifies it a bit. C#

        public string[] FindWords(string[] words) 
        {
            int[] row1 = ToCountArr("qwertyuiop");
            int[] row2 = ToCountArr("asdfghjkl");
            int[] row3 = ToCountArr("zxcvbnm");
            
            return words.Where(w => All(row1, w) || All(row2, w) || All(row3, w)).ToArray();
        }
        
        public int[] ToCountArr(string s)
        {
            int[] arr = new int[26];
            foreach (char c in s)
            {
                arr[c - 'a'] = 1;
            }
            return arr;
        }
        
        public bool All(int[] row, string input)
        {
            foreach (char c in input.ToLower())
            {
                if (row[c-'a'] == 0) return false;
            }
            return true;
        }
    

  • 10
    G

    here is my solution

    	public static String[] findWords(String[] words){
    		String s1="qwertyuiop",s2="asdfghjkl",s3="zxcvbnm";
    		List<String> list=new ArrayList<String>();
    		int count1=0,count2=0,count3=0;
    		for(int i=0;i!=words.length;i++){
    			for(int j=0;j!=words[i].length();j++){
    				if(s1.indexOf(words[i].toLowerCase().charAt(j))!=-1 ){
    					count1++;
    				}
    				if(s2.indexOf(words[i].toLowerCase().charAt(j))!=-1){
    					count2++;
    				}
    				if(s3.indexOf(words[i].toLowerCase().charAt(j))!=-1){
    					count3++;
    				}
    			}
    			if(count1==words[i].length() || count2==words[i].length() || count3==words[i].length()){
    				list.add(words[i]);
    			}
    			count1=0;
    			count2=0;
    			count3=0;
    		}
    	}
    		return list.toArray(new String[0]);
    	}

  • 0
    A

    What is the runtime of this?


  • 0
    X

    @Chidong What is it meaning?
    res.toArray(new String[0])


  • 3

    @xuyue9726 A way to convert List<String> to String[]. In Java API:
    ArrayList:
    public <T> T[] toArray(T[] a)
    Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array. If the list fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this list.
    If the list fits in the specified array with room to spare (i.e., the array has more elements than the list), the element in the array immediately following the end of the collection is set to null. (This is useful in determining the length of the list only if the caller knows that the list does not contain any null elements.)


  • 0
    T

    @aakarshmadhavan You can solve this in O(n) check time if you allow for some pre-check setup.


  • 0
    J

    Here is my solution:

    public String[] findWords(String[] words) {
    String a = "qwertyuiop";
    a += a.toUpperCase();

        String b = "asdfghjkl";
        b += b.toUpperCase();
        
        String c = "zxcvbnm";
        c += c.toUpperCase();
        
        List<String> list = new ArrayList<>();
        
        for (String word: words) {
            char ch[] = word.toCharArray();
            
            String temp = "";
            
            if (a.indexOf(ch[0]) != -1) {
                temp = a;     
            } else if (b.indexOf(ch[0]) != -1) {
                temp = b;
            } else {
                temp = c;
            }
            
            boolean flag = true;
            
            for (int i = 1; i < ch.length; i++) {
                if (temp.indexOf(ch[i]) == -1) {
                    flag = false;    
                    
                    break;
                }
            }
            
            if (flag) {
                list.add(word);
            }
        }
        
        return list.toArray(new String[0]);
    }

  • 2

    Similar solution using hashset. Looks stupid.

    public String[] findWords(String[] words) {
            if(words == null || words.length == 0) return new String[0];
            HashSet<Character>[] keyboard = new HashSet[3];
            keyboard[0] = new HashSet<Character>(Arrays.asList('q','w','e','r','t','y','u','i','o','p','Q','W','E','R','T','Y','U','I','O','P'));
            keyboard[1] = new HashSet<Character>(Arrays.asList('a','s','d','f','g','h','j','k','l','A','S','D','F','G','H','J','K','L'));
            keyboard[2] = new HashSet<Character>(Arrays.asList('z','x','c','v','b','n','m','Z','X','C','V','B','N','M'));
            
            List<String> ret = new ArrayList<String>();
            for(String w : words){
                int idx = -1;
                for(int i = 0; i < 3; i ++){
                    if(keyboard[i].contains(w.charAt(0))){
                        idx = i;
                        break;
                    }
                }
                int i = 1;
                for(; i < w.length(); i ++){
                    if(!keyboard[idx].contains(w.charAt(i))) break;
                }
                if(i == w.length()) ret.add(w);
            }
            
            String[] res = new String[ret.size()];
            for(int i = 0; i < res.length; i ++){
                res[i] = ret.get(i);
            }
            return res;
        }
    

  • 0
    K

    Using pre-calculated bitmaps, where each row is represented using only a single int per row, is another cool way:

    public class Solution {
        public String[] findWords(String[] words) {
            int[] rows = {22790416, 265961, 44052486};
            
            String[] intermediary = new String[words.length];
            int len = 0;
            for (String word : words) {
                int rowNum = -1;
                boolean pass = true;
                for (char c : word.toLowerCase().toCharArray()) {
                    int cBitmap = 1 << (c - 'a');
                    for (int j = 0; rowNum == -1; j ++) {
                        if ((rows[j] & cBitmap) != 0) {
                            rowNum = j;
                        }
                    }
                    if ((rows[rowNum] & cBitmap) == 0) {
                        pass = false;
                        break;
                    }
                }
                
                if (pass) {
                    intermediary[len] = word;
                    len ++;
                }
            }
            
            String[] results = new String[len];
            System.arraycopy(intermediary, 0, results, 0, len);
            return results;
        }
    }
    

  • 0
    B
        Map<Character, Integer> map = new HashMap() {{
           put('q', 1);
           put('w', 1);
           put('e', 1);
           put('r', 1);
           put('t', 1);
           put('y', 1);
           put('u', 1);
           put('i', 1);
           put('o', 1);
           put('p', 1);
           put('a', 2);
           put('s', 2);
           put('d', 2);
           put('f', 2);
           put('g', 2);
           put('h', 2);
           put('j', 2);
           put('k', 2);
           put('l', 2);
           put('z', 3);
           put('x', 3);
           put('c', 3);
           put('v', 3);
           put('b', 3);
           put('n', 3);
           put('m', 3);
        }};
        
        public String[] findWords(String[] words) {
            List<String> resList = new ArrayList<>();
    outter: for (String s: words) {
                String ls = s.toLowerCase();
                int row = map.get(ls.charAt(0));
                for (char c: ls.toCharArray())
                    if (row != map.get(c))
                        continue outter;
                resList.add(s);
            }
            return resList.toArray(new String[0]);
        }
    

  • 0
    E

    Don't know if it worth posting, but i think this triple-for bruteforce looks a little simplier then others. 4ms.

    		
    		
    		ArrayList<String> answer = new ArrayList<>();
    		
    		
    		for(String word : words) {
    			
    			int length = word.length()-1;
    			
    			char [] wordChar = word.toLowerCase().toCharArray();
    			
    			for(String row : rows) {
    				for(int i = 0; i< wordChar.length; i++) {
    					if(row.indexOf(wordChar[i]) == -1){ // if there's no such char in a row
    						break;
    					} else if (i ==  length){ //if word length equals iteration
    						System.out.println("char:" + wordChar[i]);						
    						answer.add(word);
    					}
    				}
    			}
    		}
    		
    		return answer.toArray(new String[answer.size()]);```

  • 0
    S
    public class Solution {
        public String[] findWords(String[] words) {
            List<String> list = new ArrayList<>();
            int[] hash = new int[26];
            String[] rows = {"qwertyuiop","asdfghjkl","zxcvbnm"};
            
            for (int i=0; i<rows.length; i++) {
                for (char c : rows[i].toCharArray()) 
                    hash[c-'a'] += i;
            }
            
            for (String word : words) {
                char first = Character.toLowerCase(word.charAt(0));
                for (int i=1; i<=word.length(); i++) {
                    if (i == word.length()) {
                       list.add(word);
                       break;
                    }
                    char c = Character.toLowerCase(word.charAt(i));
                    if( hash[c-'a'] != hash[first-'a'])
                        break;
                }
                
            }
            return list.toArray(new String[0]);
        }
    }
    

  • 0
    M

    Cool, I find the shadow of my solution here, but the detail is different. how can reduce time complexity any more?


  • 1

    My two cents

        public String[] findWords(String[] words) {
          Set<Character> row1 = stringToCharSet("qwertyuiop"); 
          Set<Character> row2 = stringToCharSet("asdfghjkl");
          Set<Character> row3 = stringToCharSet("zxcvbnm");
          
          List<String> res = new ArrayList();
          for(String word: words){
            if(isValid(row1, word) || isValid(row2, word) || isValid(row3, word)){
              res.add(word);    
            }
          }
          
          return res.toArray(new String[0]);
        }
        
        boolean isValid(Set<Character> row, String word){
          for(char c: word.toCharArray()){
            if(!row.contains(Character.toLowerCase(c))) return false;  
          }    
          return true;
        }
        
        Set<Character> stringToCharSet(String str){
          Set<Character> set = new HashSet();
          for(char c: str.toCharArray()){
            set.add(c);  
          }
          return set;
        }

  • 0
    I

    A short solution : 3ms

    public String[] findWords(String[] words) {
        String[] rows = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
        ArrayList<String> oneRowWords = new ArrayList<>();
    
        outer:
        for (String s : words) {
            int rowNum = 0;
            for (char c : s.toLowerCase().toCharArray()) {
                for( int i = 0; i < 3; i++) {
                    if (rows[i].indexOf(c) != -1) {
                        if (rowNum == 0) {
                            rowNum = i + 1;
                        } else if (rowNum != i + 1) {
                            continue outer;
                        }
                    }
                }
            }
            oneRowWords.add(s);
        }
        return oneRowWords.toArray(new String[0]);
    }

  • 0
    R

    @ilmentore Your code dose not check for the capitals!
    rows should be:

    String[] rows = {"QWERTYUIOPqwertyuiop", "ASDFGHJKLasdfghjkl", "ZXCVBNMzxcvbnm"};

    try input ["He","bAn"] and see the result.


  • 0
    I

    @robin2503 or
    ...
    char c : s.toLowerCase().toCharArray()
    ...


Log in to reply
 

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