500. Keyboard Row

Leetcode Hash Table

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:

Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Note:

1. You may use one character in the keyboard more than once.
2. You may assume the input string will only contain letters of alphabet.

分析

把键盘中的每一个字符都存在哈希表中，第$i$行字符对应数字$i$。依次检查输入的每个字符串，如果字符串的每个字符都对应相同的数字，则加入到结果中。

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 ArrayList<>();
    for (String w: words){
        if (w.length() == 0) continue;
        String wUpperCase = w.toUpperCase();
        int index = map.get(wUpperCase.charAt(0));
        for (char c: wUpperCase.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]);
}

也可以使用正则表达式和Java8新特性:

public String[] findWords(String[] words) {
    return Stream
        .of(words)
        .filter(s -> s.toLowerCase().matches("[qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*"))
        .toArray(String[]::new);
}

*表示匹配前面的子表达式零次或多次，|指明两项之间的一个选择，[]定义匹配的字符范围。