Keyboard Row Leetcode Solution

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:

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.

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.

Space Complexity

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