键盘行

题目描述

给你一个字符串数组 words，请你找出并返回可以在美式键盘的同一行字母（不考虑大小写）上打印出来的所有单词。
美式键盘的三行字母如下：

• 第一行："qwertyuiop"
• 第二行："asdfghjkl"
• 第三行："zxcvbnm"

示例 1
输入：words = ["Hello","Alaska","Dad","Peace"]
输出：["Alaska","Dad"]
说明："Alaska" 和 "Dad" 的所有字母都在同一行键盘上。

示例 2
输入：words = ["omk"]
输出：[]

解题思路详解

这个问题本质上是检查每个单词的所有字母是否来自键盘的同一行。
我们可以用哈希表建立每个字母到其所在行号的映射，然后遍历每个单词的字母，检查它们映射的行号是否全部相同。

步骤分解

1. 建立字母到行号的映射

键盘的三行字母是固定的，我们可以把它们存入三个字符串中：

row1 = "qwertyuiop"
row2 = "asdfghjkl"
row3 = "zxcvbnm"

然后，我们可以创建一个哈希表（字典），把每个字母（包括大写和小写）映射到它所在的行号（比如 1、2、3）。

为什么需要包括大写？
因为题目输入单词可能首字母大写，但判断时忽略大小写，所以我们可以统一将字母转成小写后再处理。

2. 遍历每个单词，检查字母行号一致性

对每个单词：

• 先取出它的第一个字母，找到它在哈希表中的行号。
• 然后依次检查单词中其他字母的行号是否与第一个字母的行号相同。
• 如果所有字母行号都相同，就把这个单词加入结果列表。

3. 代码实现（逐步解释）

首先，定义三行键盘字母，并创建映射字典：

def findWords(words):
    # 键盘行定义
    row1 = set("qwertyuiop")
    row2 = set("asdfghjkl")
    row3 = set("zxcvbnm")
    
    # 建立字母到行号的映射
    char_to_row = {}
    for ch in row1:
        char_to_row[ch] = 1
    for ch in row2:
        char_to_row[ch] = 2
    for ch in row3:
        char_to_row[ch] = 3

因为输入可能有大小写，我们可以在检查时统一转成小写：

    result = []
    for word in words:
        if not word:  # 空单词跳过
            continue
        # 将单词转成小写
        lower_word = word.lower()
        # 取第一个字母的行号
        first_row = char_to_row[lower_word[0]]
        # 检查后续字母
        same_row = True
        for ch in lower_word:
            if char_to_row[ch] != first_row:
                same_row = False
                break
        if same_row:
            result.append(word)
    return result

4. 优化与细节

• 我们可以提前将三行字母存为集合，这样在建立映射时更直观。
• 检查单词时，如果遇到行号不一致，可以立即跳出循环，避免无效遍历。
• 时间复杂度：O(N*L)，其中 N 是单词数量，L 是单词平均长度，每个字母只需一次哈希查找，效率很高。

5. 完整代码示例

def findWords(words):
    row1 = set("qwertyuiop")
    row2 = set("asdfghjkl")
    row3 = set("zxcvbnm")
    
    char_row = {}
    for c in row1:
        char_row[c] = 1
    for c in row2:
        char_row[c] = 2
    for c in row3:
        char_row[c] = 3
    
    res = []
    for w in words:
        if not w:
            continue
        lower_w = w.lower()
        row = char_row[lower_w[0]]
        valid = True
        for c in lower_w:
            if char_row[c] != row:
                valid = False
                break
        if valid:
            res.append(w)
    return res

6. 测试验证

用题目给的例子测试：

print(findWords(["Hello","Alaska","Dad","Peace"]))
# 输出：['Alaska', 'Dad']

• "Hello"：h 在第二行，e 在第二行，l 在第三行 → 不通过
• "Alaska"：全在第二行 → 通过
• "Dad"：全在第二行 → 通过
• "Peace"：p 在第一行，e 在第二行 → 不通过

结果符合预期。

总结

这道题的关键是：

1. 用哈希表建立字母到行号的快速映射。
2. 统一转小写以忽略大小写差异。
3. 逐个单词检查字母行号是否一致。

这是一种典型的“哈希表用于分组/归类”的应用，能高效解决此类字母归属判断问题。