Store line numbers in an array.


  • 0
    H

    I saw many solution store the keyboard layout as follow,

    String[] strs = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
    

    or,

    char[] line1 = new char[]{'q','w','e','r','t','y','u','i','o','p'};
    char[] line2 = new char[]{'a','s','d','f','g','h','j','k','l'};
    char[] line3 = new char[]{'z','x','c','v','b','n','m'};
    

    but in that way, we have to iterate several characters to find the right one.

    A better way is to store the line number in an int[]. Thus we can search line number in O(1) time.

    int[] keyboard = new int[]{2,3,3,2,1,2,2,2,1,2,2,2,3,3,1,1,1,1,2,1,1,3,1,3,1,3};
    

    here is the entire solution, 3ms.

    class Solution {
            private static final int[] LETTER = new int[]{2,3,3,2,1,2,2,2,1,2,2,2,3,3,1,1,1,1,2,1,1,3,1,3,1,3};
            private static String[] local = new String[0];
            public String[] findWords(String[] words) {
                local = words;
                int j = 0;
                for (int i = 0; i < words.length; i++) {
                    if (isOneRow(words[i])) { exch(i,j++); }
                }
                return Arrays.copyOfRange(words,0,j);
            }
            private boolean isOneRow(String s) {
                int len = s.length();
                if (len == 0) { return true; }
                int line = LETTER[getOffset(s.charAt(0))];
                for (int i = 1; i < len; i++) {
                    if (LETTER[getOffset(s.charAt(i))] != line) { return false; }
                }
                return true;
            }
            private void exch(int x, int y) {
                String temp = local[x];
                local[x] = local[y];
                local[y] = temp;
            }
            private int getOffset(char c) {
                if (c >= 'a' && c <= 'z') {
                    return c - 'a';
                } else if (c >= 'A' && c <= 'Z') {
                    return c - 'A';
                } else {
                    return -1;
                }
            }
    }
    

Log in to reply
 

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