500. 键盘行
题目描述
给你一个字符串数组 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]
由英文字母(小写和大写字母)组成
解法
方法一:字符映射
我们将每个键盘行的字符映射到对应的行数,然后遍历字符串数组,判断每个字符串是否都在同一行即可。
时间复杂度 $O(L)$,空间复杂度 $O(C)$。其中 $L$ 为所有字符串的长度之和;而 $C$ 为字符集的大小,本题中 $C = 26$。
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
方法二
1 2 3 4 5 6 7 8 9 |
|