键盘行
难度:
标签:
题目描述
给你一个字符串数组 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]
由英文字母(小写和大写字母)组成
代码结果
运行时间: 24 ms, 内存: 0.0 MB
/*
题目思路:
1. 使用Stream流处理,将每个单词映射为一个布尔值,表示它是否可以由键盘同一行字符输入。
2. 过滤出可以由同一行字符输入的单词,并转换为数组。
*/
import java.util.Arrays;
import java.util.Set;
import java.util.stream.Collectors;
public class Solution {
public String[] findWords(String[] words) {
// 定义键盘行集合
Set<Character> row1 = "qwertyuiopQWERTYUIOP".chars().mapToObj(c -> (char)c).collect(Collectors.toSet());
Set<Character> row2 = "asdfghjklASDFGHJKL".chars().mapToObj(c -> (char)c).collect(Collectors.toSet());
Set<Character> row3 = "zxcvbnmZXCVBNM".chars().mapToObj(c -> (char)c).collect(Collectors.toSet());
return Arrays.stream(words)
.filter(word -> {
if (word.isEmpty()) return false;
Set<Character> targetRow;
if (row1.contains(word.charAt(0))) {
targetRow = row1;
} else if (row2.contains(word.charAt(0))) {
targetRow = row2;
} else {
targetRow = row3;
}
return word.chars().allMatch(c -> targetRow.contains((char)c));
})
.toArray(String[]::new);
}
}
解释
方法:
该题解的思路是先将美式键盘的三行字母分别存入三个集合set_h、set_m、set_l中。然后遍历单词列表words,对于每个单词,统计其中出现的字符,存入集合check_set。最后判断check_set与set_h、set_m、set_l三个集合的并集,如果并集的大小等于set_h、set_m或set_l任一集合的大小,说明该单词的所有字母都在同一行,将其加入结果列表result中返回。
时间复杂度:
O(n*m)
空间复杂度:
O(m+n)
代码细节讲解
🦆
题解中提到,判断单词中的所有字母是否在同一行,是通过将单词的字母集合与每行的集合进行并集操作后比较大小。这种方法是否总是准确?是否有可能出现字母集合包含非该行字母但并集大小相等的情况?
▷🦆
在题解中,为什么要将键盘的每一行字母初始化为集合而不是列表或元组?使用集合有什么特别的优势吗?
▷🦆
在实现判断逻辑时,题解使用了三次并集操作和长度比较来决定单词是否符合条件。是否有更高效的方法来减少这些操作次数?
▷🦆
题解实现中考虑了字母大小写,这是否是必要的?如果输入数据保证了只有小写或大写字母,是否可以简化代码?
▷