LeetCode 题解工作台
键盘行
给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。 请注意 ，字符串 不区分大小写 ，相同字母的大小写形式都被视为在同一行 。 美式键盘 中： 第一行由字符 "qwertyuiop" 组成。 第二行由字符 "asdfghjkl" 组成。 第三行…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们将每个键盘行的字符映射到对应的行数，然后遍历字符串数组，判断每个字符串是否都在同一行即可。 时间复杂度 ，空间复杂度 。其中 为所有字符串的长度之和；而 为字符集的大小，本题中 $C = 26$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。
请注意，字符串 不区分大小写，相同字母的大小写形式都被视为在同一行。
美式键盘 中：
- 第一行由字符
"qwertyuiop"组成。 - 第二行由字符
"asdfghjkl"组成。 - 第三行由字符
"zxcvbnm"组成。
示例 1：
输入：words = ["Hello","Alaska","Dad","Peace"]
输出：["Alaska","Dad"]
解释：
由于不区分大小写，"a" 和 "A" 都在美式键盘的第二行。
示例 2：
输入：words = ["omk"]
输出：[]
示例 3：
输入：words = ["adsdf","sfd"]
输出：["adsdf","sfd"]
提示：
1 <= words.length <= 201 <= words[i].length <= 100words[i]由英文字母（小写和大写字母）组成
解题思路
方法一：字符映射
我们将每个键盘行的字符映射到对应的行数，然后遍历字符串数组，判断每个字符串是否都在同一行即可。
时间复杂度 ，空间复杂度 。其中 为所有字符串的长度之和；而 为字符集的大小，本题中 。
class Solution:
def findWords(self, words: List[str]) -> List[str]:
s1 = set('qwertyuiop')
s2 = set('asdfghjkl')
s3 = set('zxcvbnm')
ans = []
for w in words:
s = set(w.lower())
if s <= s1 or s <= s2 or s <= s3:
ans.append(w)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * m), where n is the number of words and m is the average word length, because each letter is checked once. Space complexity is O(1) for the row map plus O(k) for the output list, where k is the number of valid words. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect quick mapping of letters to rows with hash structures.
- question_mark
Look for handling both uppercase and lowercase consistently.
- question_mark
Check awareness of scanning each word efficiently without redundant operations.
常见陷阱
外企场景- error
Failing to handle case-insensitivity by not converting letters to lowercase.
- error
Incorrectly checking only the first letter instead of verifying all letters in a word.
- error
Using nested loops unnecessarily, increasing time complexity beyond linear scanning.
进阶变体
外企场景- arrow_right_alt
Return the indices of words instead of the words themselves if they can be typed on one row.
- arrow_right_alt
Allow words that can use letters from at most two rows instead of strictly one.
- arrow_right_alt
Adapt the solution for different keyboard layouts, such as Dvorak or QWERTZ.