题目描述

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

样例

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

说明

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

算法

(模拟) $O(S)$

• 提前建立三个字符串存储每一行的字母，然后对每个单词的分别用这三个字符串检验是否所有字母均出现在同一字符串里。

时间复杂度

• 每个单词的每个字母都要被遍历三次，故时间复杂度为 $O(S)$，$S$ 为整个单词表的大小。

C++ 代码

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        vector<string> rows({"qwertyuiop", "asdfghjkl", "zxcvbnm"});
        vector<string> ans;

        for (auto str : words) {
            for (int i = 0; i < 3; i++) {
                bool flag = true;
                for (auto c : str) {
                    if (c >= 'A' && c <= 'Z')
                        c = c - 'A' + 'a';
                    if (rows[i].find(c) == string::npos) {
                        flag = false;
                        break;
                    }
                }

                if (flag) {
                    ans.push_back(str);
                    break;
                }
            }
        }

        return ans;
    }
};