Keyboard Row Leetcode Solution  

Difficulty Level Easy
Frequently asked in Mathworks
algorithms coding Hashing Interview interviewprep LeetCode LeetCodeSolutions String

Problem Statement  

In this problem, we are given an array of strings. We need to find which strings in the given array belong to any same row in the QWERTY keyboard as shown below:

Keyboard Row Leetcode SolutionPin

We assume that the array contains strings of English letters.

Example

String_Array = {"Anand" , "Soni" , "Ashfak" , "Turipo"}
Ashfaq Turipo
String_Array = {"qaz" , "wsx" , "edc"}
No words found

Approach(Hashing)  

The approach is pretty straightforward. We can hash all the indices to their rows and check that every character for every string in the array has the same value hashed to it. But we need to hash for all 26 characters first in order to preprocess the hashing part. Based on that, we can store them in an array and return it.

Please click Like if you loved this article?

Algorithm

  1. Create a HashMap<Character, Integer> rowId and an array result to store resultant strings
  2. Initialize a boolean variable same_row = true to run checks on strings
  3. Hash all the characters to their rows
  4. For every string str in the array:
    • set same_row = true
    • For every character chr in the array starting from the second:
      • If the rowId[chr] is not equal to rowId[first_character]:
        • set same_row = false and jump to next string
    • If same_row == true:
      • Push it to result
  5. Return result

Implementation of Keyboard Row Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

vector <string> findWords(vector <string> &words)
{
    unordered_map <char , int> rowId;

    string temp = "qwertyuiopQWERTYUIOP";
    for(char &i : temp)
        rowId[i] = 1;

    temp = "asdfghjklASDFGHJKL";
    for(char &i : temp)
        rowId[i] = 2;

    temp = "zxcvbnmZXCVBNM";
    for(char &i : temp)
        rowId[i] = 3;

    bool same_row;

    vector <string> result;
    for(string &word : words)
    {
        same_row = true;
        for(int i = 1 ; i < word.size() ; i++)
        {
            if(rowId[word[i]] != rowId[word[0]])
            {
                same_row = false;
                break;
            }
        }
        if(same_row)
            result.push_back(word);
    }
    return result;
}

int main()
{
    vector <string> words = {"Anand" , "Soni" , "Ashfak" , "Turipo"};
    vector <string> result = findWords(words);
    for(string &word : result)
        cout << word << " ";
    return 0;
}

Java Program

import java.util.*;

class keyboard_row
{
    public static void main(String args[])
    {
        String[] words = {"Anand" , "Soni" , "Ashfak" , "Turipo"};
        String result[] = findWords(words);
        for(String word : result)
            System.out.print(word + " ");
    }

    static String[] findWords(String[] words)
    {
        HashMap <Character , Integer> rowId = new HashMap <>();

        String temp = "qwertyuiopQWERTYUIOP";
        for(char i : temp.toCharArray())
            rowId.put(i , 1);

        temp = "asdfghjklASDFGHJKL";
        for(char i : temp.toCharArray())
            rowId.put(i , 2);

        temp = "zxcvbnmZXCVBNM";
        for(char i : temp.toCharArray())
            rowId.put(i , 3);

        boolean same_row;

        List <String> result_list = new ArrayList<String>();


        for(String word : words)
        {
            same_row = true;
            for(int i = 1 ; i < word.length() ; i++)
            {
                if(rowId.get(word.charAt(i)) != rowId.get(word.charAt(0)))
                {
                    same_row = false;
                    break;
                }
            }
            if(same_row)
                    result_list.add(word);
        }

        String[] result = new String[result_list.size()];
        for(int i = 0 ; i < result.length ; i++)
            result[i] = result_list.get(i);

        return result;
    }
}
Ashfak Turipo

Complexity Analysis of Keyboard Row Leetcode Solution

Time Complexity

O(N) as we traverse through every character of every string in the array. N = sum of lengths of all strings.

See also
Ugly Number Leetcode Solution

Space Complexity

O(1) as we constant space in the memory irrespective of the memory.

Please click Like if you loved this article?

1