0500. Keyboard Row
==================
题目信息
--------
:题号: 0500
:难度: Easy
:主题: QWERTY 键盘、单行字母、大小写忽略、单词筛选
:原题: `LeetCode 0500 `_
:重点: 单词的全部字母必须来自同一键盘行、判断时忽略大小写、返回原单词及原顺序
题目重述
--------
标准美式 QWERTY 键盘的三行字母分别是 ``QWERTYUIOP``、``ASDFGHJKL`` 和 ``ZXCVBNM``。给定单词数组 ``words``,返回所有能够只使用其中同一行字母输入的单词。
判断所属键盘行时忽略字母大小写,但返回结果必须保留输入单词原来的拼写和大小写,并按它们在 ``words`` 中的原顺序排列。``words.length`` 位于 ``[1, 20]``,每个单词长度位于 ``[1, 100]``,只包含大小写英文字母。
自建示例
--------
筛选来自单一键盘行的单词:
.. code-block:: text
输入:words = ["Gas", "Tree", "Mom", "quiz"]
输出:["Gas", "Tree"]
解释:Gas 的字母都在键盘中行,Tree 的字母都在上行;Mom 和 quiz 分别跨越多行。
大小写不影响判断:
.. code-block:: text
输入:words = ["TYPE", "sad"]
输出:["TYPE", "sad"]
解释:TYPE 全部来自上行,sad 全部来自中行,返回时保留原大小写。
先建立字母到键盘行的映射
------------------------
把三行键盘字母映射为行编号。检查一个单词时,以首字母(忽略大小写)确定目标行,再逐个比较其余字母的行编号;一旦出现不同编号就丢弃该单词。结果直接按输入顺序追加原字符串,因此大小写和顺序都保留。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector findWords(
std::vector& words) {
std::array row{};
const std::string keyboard[3] = {
"qwertyuiop", "asdfghjkl", "zxcvbnm"};
for (int r = 0; r < 3; ++r) {
for (char character : keyboard[r]) {
row[character - 'a'] = r;
}
}
std::vector result;
for (const std::string& word : words) {
int target = row[std::tolower(
static_cast(word[0])) - 'a'];
bool valid = true;
for (char character : word) {
int current = row[std::tolower(
static_cast(character)) - 'a'];
if (current != target) {
valid = false;
break;
}
}
if (valid) result.push_back(word);
}
return result;
}
};
代码分析
--------
行映射把大小写差异从判断中消除,结果数组仍保存原始单词。每个单词的字符最多检查一次,时间复杂度为 ``O(sum |word|)``,键盘映射和临时变量占用 ``O(1)`` 额外空间(不计返回结果)。