Go语言LeetCode500键盘行题解示例详解

目录

• 题目描述
• 思路分析
• AC 代码
• 哈希表判断字符是否出现在某一行中
• 解题思路
• 代码

题目描述

原题链接 :

500. 键盘行 - 力扣（LeetCode） (leetcode-cn.com)

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

美式键盘 中：

• 第一行由字符 "qwertyuiop" 组成。
• 第二行编程由字符 "asdfghjkl" 组成。
• 第三行由字符 "zxcvbnm" 组成。

示例 编程客栈1：

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

示例 2：

输入：words = ["omk"]
输出：[]

示例 3：

输入：words = ["adsdf","sfd"]
输出：["adsdf","sfd"]

提示：

• 1 <= words.length <= 20
• 1 <= words[i].length <= 100
• words[i] 由英文字母（小写和大写字母）组成

思路分析

审完题就觉得这道题应该不难做，但是绝对很麻烦。毕竟看着就是那种判断来判断去的。初步一看判断数组中每个字符串的每个字符就已经是双层循环了。。还有细节处理，啧啧。

这里其实可以用统一小写的，但是我直接在给定字符串就大小写都算上了，其实我想的是先做出来如果性能不行再优化，但是直接0ms就不优化了。

思路就是判断一个字符串的第一个单词属于哪一行的，接下来照着这行判断，出现这行不存在的直接break。都判断完了没有不是的加到结果集中。

因为一开始不知道结果集多长所以创建的数组和给定数组长度一样，再遍历一遍使得结果集大小正好。

AC 代码

class Solution {
    public String[] findwords(String[] words) {
        String[] res = new String[words.length];
        String fir = "qwertyuiopQWERTYUIOP";
		String sec = "asdfghjklASDFGHJKL";
		String tir = "zxcvbnmZXCVBNM";
        int k = 0;
        for(int i = 0;i<words.length;i++){
            String temp = "";
            for(int j = 0;j<words[i].length();j++){
                if(fir.indexOf(www.devze.comwords[i].charAt(0))!=-1){
                    temp = fir;
                }else if(sec.indexOf(words[i].charAt(0))!=-1){
          编程          temp = sec;
                }else{
                    temp = tir;
                }
                if(temp.indexOf(words[i].charAt(j))==-1){
                    break;
                }
                if(temp.indexOf(words[i].charAt(j))!=-1&&j==words[i].length()-1){
                    res[k]=words[i];
                    k++;
                }
            }
        }
        String[] result = new String[k];
        for(int p = 0;p<k;p++){
            result[p] = res[p];
        }
        return result;
    }
}

哈希表判断字符是否出现在某一行中

解题思路

题目很简单，依次判断单词是不是可以在某一行键盘打出来即可。

我们先建立每行键盘的hashmap；表示该行出现过的字母。

然后判断目标单词的每个字母是否只出现在每行键盘中，具体做法遍历每个字母，都必须包含于某行的hashmap。

为了写起来方便：

            bool b1 = true;
            bool b2 = true;
            bool b3 = true;
            for (auto c: word) {
                b1 &= m1[c];
                b2 &= m2[c];
                b3 &= m3[c];
            }            
            if (b1 || b2 || b3) ans.push_back(word);

三行独立判断，有一个为真，即可在一行内打出来。

代码

class Solution {
public:
    string one = "qwertyuiopQWERTYUIOP";
    string two 开发者_JAVA开发= "asdfghjklASDFGHJKL";
    string three = "zxcvbnmZXCVBNM";
    unordered_map<char, int> m1,m2,m3;
    vector<string> findWords(vector<string>& words) {
        for (auto c: one) {
            m1[c]++;
        }
        for (auto c: two) {
            m2[c]++;
        }
        for (auto c: three) {
            m3[c]++;
        }
        vector<string> ans;
        for (auto word: words) {
            bool b1 = true;
            bool b2 = true;
            bool b3 = true;
            for (auto c: word) {
      http://www.devze.com          b1 &= m1[c];
                b2 &= m2[c];
                b3 &= m3[c];
            }
            
            if (b1 || b2 || b3) ans.push_back(word);
        }
        return ans;
    }
};

复杂度

时间复杂度： O(N)

空间复杂度： O(N)

以上就是Go语言LeetCode500键盘行题解示例详解的详细内容，更多关于Go语言题解键盘行的资料请关注我们其它相关文章！