LeetCode.500.Keyboard Row

---

题目描述

• 500 Keyboard Row
  https://leetcode.com/problems/keyboard-row/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:

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.

---

解题过程

字符串处理题，本身不难，就是略显繁琐，并且就怕用暴力方法时间复杂度太高，但想了想也没啥巧方法，试着写了一个，没想到一次通过，而且速度还不慢，打败了76.85%的sub

package _500_KeyboardRow;

import java.util.ArrayList;
import java.util.List;

class Solution {
    String firstRow="QWERTYUIOPqwertyuiop";
    String secondRow="ASDFGHJKLasdfghjkl";
    String thirdRow="ZXCVBNMzxcvbnm";
    
    public String[] findWords(String[] words) {
        List<String> resultList = new ArrayList<String>();
        for(String word:words){
            int firstLetterRow=whichRow(word.charAt(0));//第一个字符所在的行号
            int i=1;
            for(; i<word.length(); i++){
                if(whichRow(word.charAt(i)) != firstLetterRow)
                    break;
            }
            if(i == word.length())
                resultList.add(word);
        }
        return resultList.toArray(new String[0]);
    }
    
    //求ch所在的行号
    private int whichRow(char ch){
        if(firstRow.indexOf(ch) >= 0){
            return 1;
        }else if(secondRow.indexOf(ch) >= 0){
            return 2;
        }else{
            return 3;
        }
    }    
}

public class KeyboardRow {
    public static void main(String[] args){
        Solution solution = new Solution();
        String[] input = {"Hello", "Alaska", "Dad", "Peace"};
        String[] output = solution.findWords(input);
        for(String word:output){
            System.out.print(word+" ");
        }
    }
}

顺便学了下List转字符串数组的方法<T> T[] toArray(T[] a)的用法。

通过后看了看别人的代码，好多也都是挨个遍历看在哪行，有一部分是用map，典型代码如下：

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

我感觉也不算太简单，只不过用了稍高级的数据结构。后来看到这道题被打上了哈希表的标签，那看来出题人就是想让用Map来解决。

Discuss里比较牛逼的是被顶的最高的一个帖子，Java版单行代码：

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

用到了java8里新增的Stream流，还有正则表达式匹配，很高端，顺便看了看Stream是怎么用的。

---

GitHub代码

• 500 Keyboard Row
  https://github.com/masikkk/algorithms/tree/master/leetcode/leetcode/_500_KeyboardRow

---