KeyboardRow [source code]

public class KeyboardRow {
    private final List<Character> letters = Arrays.asList(
            'q','w','e','r','t','y','u','i','o','p',
            'a','s','d','f','g','h','j','k','l',
            'z','x','c','v','b','n','m');

    public String[] findWords(String[] words) {
        List<String> result = new ArrayList<>();
        for (String word : words ) {
            int minRow = 3;
            int maxRow = 1;  
            for (int i = 0; i < word.length(); i++) {
                int charLocation = findRow(word.toLowerCase().charAt(i));
                minRow = Math.min(charLocation, minRow);
                maxRow = Math.max(charLocation, maxRow);
            }
            if (maxRow - minRow > 0) continue;
            result.add(word);
        }
        return result.toArray(new String[0]);
    }

    private int findRow(char charArg) {
        int index = letters.indexOf(charArg);
        int rowNo = 0;
        if (index < 10) rowNo = 1;
        else if (index < 19) rowNo = 2;
        else rowNo = 3;
        return rowNo;
    }
}

最开始这里犯了一个很低级的失误,就是 min 和 max 一开始都是给的0,这个直接导致后面的完全跑不起来; 这里学到的经验有两点:

1. buffer 一定要proper initialization,这个其实前面也提到过的了.一定要proper initialization才能保证后面的 loop 可以正确开始;
2. 实在想不通的时候,自己一个一个的写 trace. 编程无非是数学, 一个数字一个数字的写就行了.

另外这一题还总结一个思路: 虽然看起来给你的输入各种 string 什么的,但是编程无非是数学,如果能够转化为数字来做,往往问题会简单很多,就像这一题我这里的思路就是转换为数字.

另外,这里这个 findRow 里面,一开始我写的时候,if 的三个 branch,每个里面直接 return,但是这个不好. 要养成函数开始直接先给return value buffer的习惯. 这样一个很大的好处即使 debug 的时候方便很多,方便添加 print.

另外这个算法最后的速度只有30%, 所以应该还是有更好的解法的.

不过时间的绝对值其实只有6ms, 所以这个问题上纠结太久其实也没什么意思;

这个是另外一个算法:

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]);  
    }  
}

基本思路就是先把每个字母的row number都记录下来, 扔到一个 map 里面, 然后把 words 过一遍就行了.

Problem Description

Given a List of words, return the words that can be typed using letters of alphabet on only one row's of American keyboard like the image below.
Example 1:
Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]
Note:
You may use one Character in the keyboard more than once.
You may assume the input string will only contain letters of alphabet.