Keyboard Row

Problem

Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below.

Note that the strings are case-insensitive , both lowercased and uppercased of the same letter are treated as if they are at the same row.

In the American keyboard :

the first row consists of the characters "qwertyuiop",
the second row consists of the characters "asdfghjkl", and
the third row consists of the characters "zxcvbnm".

Examples

Example 1

1
2
3
4
5
6
7
8
9



Input: words = ["Hello","Alaska","Dad","Peace"]

Output: ["Alaska","Dad"]

Explanation:

Both `"a"` and `"A"` are in the 2nd row of the American keyboard due to case
insensitivity.

Example 2

1
2
3
4



Input: words = ["omk"]

Output: []

Example 3

1
2
3
4



Input: words = ["adsdf","sfd"]

Output: ["adsdf","sfd"]

Constraints

1 <= words.length <= 20
1 <= words[i].length <= 100
words[i] consists of English letters (both lowercase and uppercase).

Solution

Method 1 – Hash Set Row Mapping

Intuition

Each letter belongs to a specific keyboard row. If all letters of a word belong to the same row, the word is valid. We can map each letter to its row and check each word.

Approach

Create a mapping from each letter (case-insensitive) to its keyboard row (1, 2, or 3).
For each word, check if all its letters map to the same row.
Collect and return all such words.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        vector<string> rows = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
        unordered_map<char, int> mp;
        for (int i = 0; i < 3; ++i)
            for (char c : rows[i]) mp[c] = i, mp[toupper(c)] = i;
        vector<string> ans;
        for (auto& w : words) {
            int row = mp[w[0]];
            bool ok = true;
            for (char c : w) if (mp[c] != row) { ok = false; break; }
            if (ok) ans.push_back(w);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func findWords(words []string) []string {
    row := map[rune]int{}
    for _, c := range "qwertyuiop" { row[c] = 1; row[c-'a'+'A'] = 1 }
    for _, c := range "asdfghjkl" { row[c] = 2; row[c-'a'+'A'] = 2 }
    for _, c := range "zxcvbnm" { row[c] = 3; row[c-'a'+'A'] = 3 }
    ans := []string{}
    for _, w := range words {
        r := row[rune(w[0])]
        ok := true
        for _, c := range w {
            if row[c] != r { ok = false; break }
        }
        if ok { ans = append(ans, w) }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    public String[] findWords(String[] words) {
        String[] rows = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
        Map<Character, Integer> mp = new HashMap<>();
        for (int i = 0; i < 3; ++i)
            for (char c : rows[i].toCharArray()) {
                mp.put(c, i); mp.put(Character.toUpperCase(c), i);
            }
        List<String> ans = new ArrayList<>();
        for (String w : words) {
            int row = mp.get(w.charAt(0));
            boolean ok = true;
            for (char c : w.toCharArray()) if (mp.get(c) != row) { ok = false; break; }
            if (ok) ans.add(w);
        }
        return ans.toArray(new String[0]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    fun findWords(words: Array<String>): Array<String> {
        val rows = arrayOf("qwertyuiop", "asdfghjkl", "zxcvbnm")
        val mp = mutableMapOf<Char, Int>()
        for (i in 0..2) for (c in rows[i]) { mp[c] = i; mp[c.uppercaseChar()] = i }
        val ans = mutableListOf<String>()
        for (w in words) {
            val row = mp[w[0]]
            if (w.all { mp[it] == row }) ans.add(w)
        }
        return ans.toTypedArray()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def findWords(self, words: list[str]) -> list[str]:
        row1 = set('qwertyuiop')
        row2 = set('asdfghjkl')
        row3 = set('zxcvbnm')
        ans = []
        for w in words:
            s = set(w.lower())
            if s <= row1 or s <= row2 or s <= row3:
                ans.append(w)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


use std::collections::HashMap;
impl Solution {
    pub fn find_words(words: Vec<String>) -> Vec<String> {
        let rows = ["qwertyuiop", "asdfghjkl", "zxcvbnm"];
        let mut mp = HashMap::new();
        for (i, row) in rows.iter().enumerate() {
            for c in row.chars() {
                mp.insert(c, i);
                mp.insert(c.to_ascii_uppercase(), i);
            }
        }
        let mut ans = vec![];
        'outer: for w in &words {
            let row = mp[&w.chars().next().unwrap()];
            for c in w.chars() {
                if mp[&c] != row { continue 'outer; }
            }
            ans.push(w.clone());
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
    findWords(words: string[]): string[] {
        const rows = ["qwertyuiop", "asdfghjkl", "zxcvbnm"];
        const mp = new Map<string, number>();
        for (let i = 0; i < 3; ++i)
            for (const c of rows[i]) { mp.set(c, i); mp.set(c.toUpperCase(), i); }
        const ans: string[] = [];
        for (const w of words) {
            const row = mp.get(w[0]);
            if ([...w].every(c => mp.get(c) === row)) ans.push(w);
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n * m), where n is the number of words and m is the average word length. Each letter is checked once.
🧺 Space complexity: O(1), for the row mapping (constant size).

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Hash Set Row Mapping#

Intuition#

Approach#

Code#

Complexity#