Go語言LeetCode500鍵盤行題解示例詳解

更新時間：2022年12月30日 10:17:27 作者：劉09k11

這篇文章主要為大家介紹了Go語言LeetCode500鍵盤行題解示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目描述

原題鏈接 :

500. 鍵盤行 - 力扣（LeetCode） (leetcode-cn.com)

給你一個字符串數(shù)組 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] 由英文字母（小寫和大寫字母）組成

思路分析

審完題就覺得這道題應該不難做，但是絕對很麻煩。畢竟看著就是那種判斷來判斷去的。初步一看判斷數(shù)組中每個字符串的每個字符就已經(jīng)是雙層循環(huán)了。。還有細節(jié)處理，嘖嘖。

這里其實可以用統(tǒng)一小寫的，但是我直接在給定字符串就大小寫都算上了，其實我想的是先做出來如果性能不行再優(yōu)化，但是直接0ms就不優(yōu)化了。

思路就是判斷一個字符串的第一個單詞屬于哪一行的，接下來照著這行判斷，出現(xiàn)這行不存在的直接break。都判斷完了沒有不是的加到結(jié)果集中。

因為一開始不知道結(jié)果集多長所以創(chuàng)建的數(shù)組和給定數(shù)組長度一樣，再遍歷一遍使得結(jié)果集大小正好。

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(words[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;
    }
}

哈希表判斷字符是否出現(xiàn)在某一行中

解題思路

題目很簡單，依次判斷單詞是不是可以在某一行鍵盤打出來即可。
我們先建立每行鍵盤的hashmap；表示該行出現(xiàn)過的字母。

然后判斷目標單詞的每個字母是否只出現(xiàn)在每行鍵盤中，具體做法遍歷每個字母，都必須包含于某行的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);

三行獨立判斷，有一個為真，即可在一行內(nèi)打出來。

代碼

class Solution {
public:
    string one = "qwertyuiopQWERTYUIOP";
    string two = "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) {
                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鍵盤行題解示例詳解的詳細內(nèi)容，更多關于Go語言題解鍵盤行的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: