leetcode
leetcode 451 ~ 500
键盘行

键盘行

难度:

标签:

题目描述

给你一个字符串数组 words ,只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

美式键盘 中:

  • 第一行由字符 "qwertyuiop" 组成。
  • 第二行由字符 "asdfghjkl" 组成。
  • 第三行由字符 "zxcvbnm" 组成。

American keyboard

 

示例 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)

代码细节讲解

🦆
题解中提到,判断单词中的所有字母是否在同一行,是通过将单词的字母集合与每行的集合进行并集操作后比较大小。这种方法是否总是准确?是否有可能出现字母集合包含非该行字母但并集大小相等的情况?
该方法是准确的。当检查集合与某一行字母集合的并集大小等于该行字母集合的大小时,意味着检查集合中的所有字母都包含在这一行中。由于集合是无重复元素的,任何额外的非行字母将会使并集的大小增加,因此不可能出现包含非该行字母却使并集大小不变的情况。
🦆
在题解中,为什么要将键盘的每一行字母初始化为集合而不是列表或元组?使用集合有什么特别的优势吗?
使用集合的主要优势在于集合提供了更高效的查找和操作时间。集合内部基于哈希表实现,使得平均时间复杂度为O(1)的成员检查和唯一性保证。如果使用列表或元组,则成员检查的时间复杂度为O(n),这在大量操作时会较为耗时。此外,集合操作如并集、交集等也非常直接和高效,适合本题中的要求。
🦆
在实现判断逻辑时,题解使用了三次并集操作和长度比较来决定单词是否符合条件。是否有更高效的方法来减少这些操作次数?
一种更高效的方法是直接判断单词的每个字母是否都属于同一个集合,而无需进行并集操作。可以通过检查单词中的第一个字母属于哪个集合,然后验证单词中的其余字母是否也都属于该集合。这样可以将三次并集操作简化为对单词的一次遍历,每个字母一次集合成员检查,大幅提高效率。
🦆
题解实现中考虑了字母大小写,这是否是必要的?如果输入数据保证了只有小写或大写字母,是否可以简化代码?
如果输入数据保证了只有小写或大写字母,那么确实可以简化代码。在这种情况下,可以只初始化一个小写或大写字母的集合,从而避免初始化和检查大小写两种形式的字母。这不仅简化了代码,还能减少运行时的内存占用和提高一些效率。

相关问题