LeetCode 500: Keyboard Row (Single-Row Letter Set Validation)
LeetCode 500StringHash SetSimulationToday we solve LeetCode 500 - Keyboard Row.
Source: https://leetcode.com/problems/keyboard-row/
English
Problem Summary
Given a list of words, return those words that can be typed using letters from only one keyboard row (American keyboard).
Key Insight
Map each character to a row id (1/2/3). For each word, the first letter determines the target row. If any other letter maps to a different row, the word is invalid.
Brute Force and Limitations
You could repeatedly search each character in three row strings and track matches, but that does extra repeated scans. A direct row map keeps checks constant-time.
Optimal Algorithm Steps
1) Build a map from lowercase letter to row id.
2) For each word, lowercase it and read row id of the first char.
3) Scan remaining chars; if any row differs, reject word.
4) Keep words that pass all checks.
Complexity Analysis
Time: O(totalCharacters).
Space: O(1) extra (fixed alphabet mapping).
Common Pitfalls
- Forgetting case normalization.
- Not handling single-letter words (they are always valid).
- Using per-character row-string search instead of precomputed mapping.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String[] findWords(String[] words) {
int[] row = new int[26];
for (char c : "qwertyuiop".toCharArray()) row[c - 'a'] = 1;
for (char c : "asdfghjkl".toCharArray()) row[c - 'a'] = 2;
for (char c : "zxcvbnm".toCharArray()) row[c - 'a'] = 3;
java.util.List<String> ans = new java.util.ArrayList<>();
for (String w : words) {
String s = w.toLowerCase();
int r = row[s.charAt(0) - 'a'];
boolean ok = true;
for (int i = 1; i < s.length(); i++) {
if (row[s.charAt(i) - 'a'] != r) {
ok = false;
break;
}
}
if (ok) ans.add(w);
}
return ans.toArray(new String[0]);
}
}func findWords(words []string) []string {
row := [26]int{}
for _, c := range "qwertyuiop" {
row[c-'a'] = 1
}
for _, c := range "asdfghjkl" {
row[c-'a'] = 2
}
for _, c := range "zxcvbnm" {
row[c-'a'] = 3
}
ans := make([]string, 0, len(words))
for _, w := range words {
s := strings.ToLower(w)
r := row[s[0]-'a']
ok := true
for i := 1; i < len(s); i++ {
if row[s[i]-'a'] != r {
ok = false
break
}
}
if ok {
ans = append(ans, w)
}
}
return ans
}class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<int> row(26, 0);
for (char c : string("qwertyuiop")) row[c - 'a'] = 1;
for (char c : string("asdfghjkl")) row[c - 'a'] = 2;
for (char c : string("zxcvbnm")) row[c - 'a'] = 3;
vector<string> ans;
for (const string& w : words) {
string s = w;
for (char& ch : s) ch = tolower(ch);
int r = row[s[0] - 'a'];
bool ok = true;
for (int i = 1; i < (int)s.size(); i++) {
if (row[s[i] - 'a'] != r) {
ok = false;
break;
}
}
if (ok) ans.push_back(w);
}
return ans;
}
};class Solution:
def findWords(self, words: List[str]) -> List[str]:
row = [0] * 26
for ch in "qwertyuiop":
row[ord(ch) - ord('a')] = 1
for ch in "asdfghjkl":
row[ord(ch) - ord('a')] = 2
for ch in "zxcvbnm":
row[ord(ch) - ord('a')] = 3
ans = []
for w in words:
s = w.lower()
r = row[ord(s[0]) - ord('a')]
ok = True
for ch in s[1:]:
if row[ord(ch) - ord('a')] != r:
ok = False
break
if ok:
ans.append(w)
return ansvar findWords = function(words) {
const row = Array(26).fill(0);
for (const ch of "qwertyuiop") row[ch.charCodeAt(0) - 97] = 1;
for (const ch of "asdfghjkl") row[ch.charCodeAt(0) - 97] = 2;
for (const ch of "zxcvbnm") row[ch.charCodeAt(0) - 97] = 3;
const ans = [];
for (const w of words) {
const s = w.toLowerCase();
const r = row[s.charCodeAt(0) - 97];
let ok = true;
for (let i = 1; i < s.length; i++) {
if (row[s.charCodeAt(i) - 97] !== r) {
ok = false;
break;
}
}
if (ok) ans.push(w);
}
return ans;
};中文
题目概述
给定一个单词数组，返回其中能仅使用美式键盘同一行字母输入的单词。
核心思路
把每个字母映射到对应行号（1/2/3）。每个单词以首字符的行号为目标行，只要后续有字符行号不同就判定失败。
暴力解法与不足
暴力法可在三行字符串里反复查每个字符，但会产生重复查找。预处理字母到行号映射后，判断更直接且常数更小。
最优算法步骤
1）构建 26 个字母到行号的映射。
2）遍历每个单词，统一转小写后读取首字符行号。
3）检查其余字符是否都在同一行。
4）通过检查的单词加入答案。
复杂度分析
时间复杂度：O(总字符数)。
空间复杂度：O(1)（固定字母映射）。
常见陷阱
- 忘记统一大小写。
- 忽略单字符单词本身总是合法。
- 未预处理映射导致字符查找重复开销。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String[] findWords(String[] words) {
int[] row = new int[26];
for (char c : "qwertyuiop".toCharArray()) row[c - 'a'] = 1;
for (char c : "asdfghjkl".toCharArray()) row[c - 'a'] = 2;
for (char c : "zxcvbnm".toCharArray()) row[c - 'a'] = 3;
java.util.List<String> ans = new java.util.ArrayList<>();
for (String w : words) {
String s = w.toLowerCase();
int r = row[s.charAt(0) - 'a'];
boolean ok = true;
for (int i = 1; i < s.length(); i++) {
if (row[s.charAt(i) - 'a'] != r) {
ok = false;
break;
}
}
if (ok) ans.add(w);
}
return ans.toArray(new String[0]);
}
}func findWords(words []string) []string {
row := [26]int{}
for _, c := range "qwertyuiop" {
row[c-'a'] = 1
}
for _, c := range "asdfghjkl" {
row[c-'a'] = 2
}
for _, c := range "zxcvbnm" {
row[c-'a'] = 3
}
ans := make([]string, 0, len(words))
for _, w := range words {
s := strings.ToLower(w)
r := row[s[0]-'a']
ok := true
for i := 1; i < len(s); i++ {
if row[s[i]-'a'] != r {
ok = false
break
}
}
if ok {
ans = append(ans, w)
}
}
return ans
}class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<int> row(26, 0);
for (char c : string("qwertyuiop")) row[c - 'a'] = 1;
for (char c : string("asdfghjkl")) row[c - 'a'] = 2;
for (char c : string("zxcvbnm")) row[c - 'a'] = 3;
vector<string> ans;
for (const string& w : words) {
string s = w;
for (char& ch : s) ch = tolower(ch);
int r = row[s[0] - 'a'];
bool ok = true;
for (int i = 1; i < (int)s.size(); i++) {
if (row[s[i] - 'a'] != r) {
ok = false;
break;
}
}
if (ok) ans.push_back(w);
}
return ans;
}
};class Solution:
def findWords(self, words: List[str]) -> List[str]:
row = [0] * 26
for ch in "qwertyuiop":
row[ord(ch) - ord('a')] = 1
for ch in "asdfghjkl":
row[ord(ch) - ord('a')] = 2
for ch in "zxcvbnm":
row[ord(ch) - ord('a')] = 3
ans = []
for w in words:
s = w.lower()
r = row[ord(s[0]) - ord('a')]
ok = True
for ch in s[1:]:
if row[ord(ch) - ord('a')] != r:
ok = False
break
if ok:
ans.append(w)
return ansvar findWords = function(words) {
const row = Array(26).fill(0);
for (const ch of "qwertyuiop") row[ch.charCodeAt(0) - 97] = 1;
for (const ch of "asdfghjkl") row[ch.charCodeAt(0) - 97] = 2;
for (const ch of "zxcvbnm") row[ch.charCodeAt(0) - 97] = 3;
const ans = [];
for (const w of words) {
const s = w.toLowerCase();
const r = row[s.charCodeAt(0) - 97];
let ok = true;
for (let i = 1; i < s.length; i++) {
if (row[s.charCodeAt(i) - 97] !== r) {
ok = false;
break;
}
}
if (ok) ans.push(w);
}
return ans;
};
Comments