【leetcode刷题】T49-键盘行

木又AI帮

修改于 2019-07-18 10:05:08

3960

修改于 2019-07-18 10:05:08

文章被收录于专栏：木又AI帮

【英文题目】（学习英语的同时，更能理解题意哟~）

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:

Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Note:

You may use one character in the keyboard more than once.
You may assume the input string will only contain letters of alphabet.

【中文题目】

给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。

示例：

输入: ["Hello", "Alaska", "Dad", "Peace"]
输出: ["Alaska", "Dad"]

注意：

你可以重复使用键盘上同一字符。
你可以假设输入的字符串将只包含字母。

【思路】

使用set储存每一行的字母，判断单词的每个字母是否在同一个set中，或者，将单词转换为set，判断其与键盘每一行字母set的差集是否为空集。

【代码】

python版本

class Solution(object):
    def findWords(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        alpha_set = [set('qwertyuiop'), set('asdfghjkl'), set('zxcvbnm')]
        res = []
        for word in words:
            tmp_set = set(word.lower())
            for s in alpha_set:
                if len(tmp_set - s) == :
                    res.append(word)
        return res

C++版本

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        vector<set<char>> alpha_set;
        alpha_set.push_back(set<char> {'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'});
        alpha_set.push_back(set<char> {'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'});
        alpha_set.push_back(set<char> {'z', 'x', 'c', 'v', 'b', 'n', 'm'});
        vector<string> res;
        for(int i=; i<words.size(); i++){
            for(int j=; j<alpha_set.size(); j++){
                int k = ;
                for(k=; k<words[i].length(); k++){
                    char w = words[i][k];
                    if(w < )
                        w += ;
                    if(alpha_set[j].find(w) == alpha_set[j].end())
                        break;
                }
                if(k == words[i].length())
                    res.push_back(words[i]);
            }
        }
        return res;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-04-24，如有侵权请联系 cloudcommunity@tencent.com 删除

python