Easy

题目描述

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

注意，字符串不区分大小写，同一个字母的大写和小写被视为在同一行。

在美式键盘中：

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

示例 1：

输入：words = ["Hello","Alaska","Dad","Peace"]
输出：["Alaska","Dad"]
解释：
由于不区分大小写，"a" 和 "A" 都在美式键盘的第2行。

示例 2：

输入：words = ["omk"]
输出：[]

示例 3：

输入：words = ["adsdf","sfd"]
输出：["adsdf","sfd"]

提示：

  • 1 <= words.length <= 20
  • 1 <= words[i].length <= 100
  • words[i] 由英文字母（大小写均可）组成

解题思路

这道题的核心思路是判断每个单词的所有字母是否都属于键盘的同一行。

解法一：哈希表映射（推荐）

  1. 创建一个哈希表，将每个字母映射到其所在的行号（0、1、2）
  2. 对于每个单词，遍历其所有字符，判断是否都在同一行
  3. 可以记录第一个字符的行号，然后检查后续字符是否与第一个字符在同一行

解法二：集合判断

  1. 将三行字符分别存储为集合
  2. 对于每个单词，将其字符转换为集合，判断是否完全包含在某一行的集合中

解法三：字符串查找 直接在三个行字符串中查找每个字符，但效率较低。

哈希表方法时间复杂度最优，代码简洁，是最推荐的解法。注意处理大小写问题，统一转换为小写字母进行比较。

代码实现

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        unordered_map<char, int> rowMap;
        string rows[3] = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
        
        // 建立字符到行号的映射
        for (int i = 0; i < 3; i++) {
            for (char c : rows[i]) {
                rowMap[c] = i;
            }
        }
        
        vector<string> result;
        for (const string& word : words) {
            if (word.empty()) continue;
            
            int targetRow = rowMap[tolower(word[0])];
            bool isValid = true;
            
            for (char c : word) {
                if (rowMap[tolower(c)] != targetRow) {
                    isValid = false;
                    break;
                }
            }
            
            if (isValid) {
                result.push_back(word);
            }
        }
        
        return result;
    }
};

class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        row_map = {}
        rows = ["qwertyuiop", "asdfghjkl", "zxcvbnm"]
        
        # 建立字符到行号的映射
        for i, row in enumerate(rows):
            for char in row:
                row_map[char] = i
        
        result = []
        for word in words:
            if not word:
                continue
            
            target_row = row_map[word[0].lower()]
            is_valid = True
            
            for char in word:
                if row_map[char.lower()] != target_row:
                    is_valid = False
                    break
            
            if is_valid:
                result.append(word)
        
        return result

public class Solution {
    public string[] FindWords(string[] words) {
        var rowMap = new Dictionary<char, int>();
        string[] rows = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
        
        // 建立字符到行号的映射
        for (int i = 0; i < 3; i++) {
            foreach (char c in rows[i]) {
                rowMap[c] = i;
            }
        }
        
        var result = new List<string>();
        foreach (string word in words) {
            if (string.IsNullOrEmpty(word)) continue;
            
            int targetRow = rowMap[char.ToLower(word[0])];
            bool isValid = true;
            
            foreach (char c in word) {
                if (rowMap[char.ToLower(c)] != targetRow) {
                    isValid = false;
                    break;
                }
            }
            
            if (isValid) {
                result.Add(word);
            }
        }
        
        return result.ToArray();
    }
}

var findWords = function(words) {
    const rowMap = new Map();
    const rows = ["qwertyuiop", "asdfghjkl", "zxcvbnm"];
    
    // 建立字符到行号的映射
    for (let i = 0; i < 3; i++) {
        for (const char of rows[i]) {
            rowMap.set(char, i);
        }
    }
    
    const result = [];
    for (const word of words) {
        if (!word) continue;
        
        const targetRow = rowMap.get(word[0].toLowerCase());
        let isValid = true;
        
        for (const char of word) {
            if (rowMap.get(char.toLowerCase()) !== targetRow) {
                isValid = false;
                break;
            }
        }
        
        if (isValid) {
            result.push(word);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
哈希表映射O(n × m)O(1)

其中 n 是单词的数量，m 是单词的平均长度。空间复杂度为 O(1) 是因为哈希表大小固定为 26 个字母。

相关题目