当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.500.Keyboard Row

LeetCode.500.Keyboard Row


题目描述

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代码


上一篇 LeetCode.682.Baseball Game

下一篇 LeetCode.191.Number of 1 Bits

阅读
604
阅读预计3分钟
创建日期 2018-01-14
修改日期 2018-01-16
类别
百度推荐