[LeetCode]Ar500. 键盘行

🚩传送门：https://leetcode-cn.com/problems/keyboard-row/

🍗鸡腿知识点：

1. 在正则表达式最前面加上 (?i) 就可以忽略后面所有的大小写
2. res.toArray(new String[res.size()]) 将list转为数组

题目

给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

美式键盘 中：

1. 第一行由字符 "qwertyuiop" 组成。
2. 第二行由字符 "asdfghjkl“ 组成。
3. 第三行由字符 "zxcvbnm" 组成。

示例 1：

输入：words = [“Hello”,”Alaska”,”Dad”,”Peace”] 输出：[“Alaska”,”Dad”]

示例 2：

输入：words = [“omk”] 输出：[]

示例 3：

输入：words = [“adsdf”,”sfd”] 输出：[“adsdf”,”sfd”]

解题思路：暴力

复杂度分析

时间复杂度：，其中 是最长的单词的长度， 为字符串的数量。

空间复杂度：，其中 为字符串的数量。

官方代码

class Solution {
    public String[] findWords(String[] words) {
        if (words == null) return null;
        //1.结果集
        List<String> ans = new ArrayList<>();
        //2.字典行
        String lines[] = new String[] {"qwertyuiop","asdfghjkl","zxcvbnm"};
        //3.挨个单词匹配是否满足条件
        for (String word : words) {
            if(judge(word.toLowerCase(),lines)) {
                ans.add(word);
            }
        }
        //4.list直接利用API转换为String数组
        return ans.toArray(new String[ans.size()]);
    }
    private boolean judge(String word,String[] lines) {
        String find = null;
        // 先用word首字符确定属于哪一行
        for (String line : lines) {
            if (line.indexOf(word.charAt(0)) > -1) {
                find = line;
                break;
            }
        }
        //word首字符非字母形式
        if (find == null) return false;
        // 判断word字符串所有字符是否都属于同一行
        for (int i = 1;i < word.length();i++) {
            if (find.indexOf(word.charAt(i)) < 0) return false;
        }
        return true;
    }
}

解题思路：正则表达式

模式固定，所以使用正则表达式。

官方代码

class Solution {
    public String[] findWords(String[] words) {
        //1.正则表达式
        String pattern="(?i)^[qwertyuiop]+|[asdfghjkl]+|[zxcvbnm]+$";
        String pattern = "^([QWERTYUIOPqwertyuiop]+|[ASDFGHJKLasdfghjkl]+|[ZXCVBNMzxcvbnm]+)$";
        //2.存放结果的res链表
        List<String> res = new ArrayList<>();
        //3.依次遍历匹配
        for(String word:words){
            if( Pattern.matches(pattern, word))
                res.add(word);
        }
        //4.转换为 String 数组输出
        return res.toArray(new String[res.size()]);
    }
}

👀 解题思路：打表映射

建立一个从字母到数字的映射，把第 行的字母映射为数字

把个单词的每个字母映射为数字后进行按位与操作，如果结果不是 0，说明字母都来自同一行。

例如：
把第一行的字母全映射为 1，也就是二进制 001 把第二行的字母全映射为 2，也就是二进制 010 把第三行的字母全映射为 4，也就是二进制 100

[q, w, e] 👉 [1, 1, 1] 👉 1 & 1 & 1 == 1 👉 同一行 [q, w, n] 👉 [1, 1, 4] 👉 1 & 1 & 4 == 0 👉 不同行

这样同一行的字母的映射值按位相与不为零，而不同行的字母映射值按位相与为零。

复杂度分析

时间复杂度：，其中 是最长的单词的长度。

空间复杂度：，其中 为字符串的数量。

官方代码

class Solution {
    public String[] findWords(String[] words) {
        // A、B、C、D、E、F、G、H、I、J、K、L、M、N、O、P、Q、R、S、T、U、V、W、X、Y、Z
          //1.打表[空间换时间]
        int []charset=new int[]{2,4,4,2,1,2,2,2,1,2,2,2,4,4,1,1,1,1,2,1,1,4,1,4,1,4};
        List<String> ans = new ArrayList<>();
        int res=0;
        //2.依次遍历数组
        for(String word:words){
            //3.将word转为小写的字符数组
            char[]chars =word.toLowerCase().toCharArray();
            //4.对应字符进行按位与操作
            for(int i=0;i<chars.length;i++){
                if(i==0) res=charset[chars[i]-'a'];
                res&=charset[chars[i]-'a'];
            }
            //5.非0值说明同一行
            if(res!=0) ans.add(word);
        }
        return ans.toArray(new String[ans.size()]);
    }
}

另类打表

class Solution {
    public String[] findWords(String[] words) {
        if(words==null||words.length==0) return new String[0];
        //1.用长度为26的数组标识每个字母所在的行号
        int[] map = {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};
        //2.结果集
        List<String> list = new ArrayList<String>();
        //3.遍历word
        for(String word:words){
            //4.转成大写
            String tempWord = word.toUpperCase();
            //5.首字母计算出当前单词应该所在的行
            int temp = map[tempWord.charAt(0)-'A'];
            boolean flag = true;
            //6.通过与首字母比较行号确定是否在同一行
            for(int i=1;i<tempWord.length();i++){
                //7.发现不在同一行,标记false
                if(temp != map[tempWord.charAt(i)-'A']){
                    flag = false;
                    break;
                }
            }
            if(flag) list.add(word);
        }
        return list.toArray(new String[list.size()]);
    }
}