कीबोर्ड रो लेटकोड समाधान


कठिनाई स्तर आसान
में अक्सर पूछा मैथवर्क्स
hashing तार

समस्या का विवरण

इस समस्या में, हमें एक दिया जाता है सरणी तार के। हमें यह खोजने की आवश्यकता है कि दिए गए एरे में कौन से तार किसी भी पंक्ति में हैं इस QWERTY नीचे दिखाए अनुसार कीबोर्ड:

कीबोर्ड रो लेटकोड समाधान

हम मानते हैं कि सरणी में अंग्रेजी अक्षरों के तार हैं।

उदाहरण

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

दृष्टिकोण (हैशिंग)

दृष्टिकोण बहुत सीधा है। हम उनकी पंक्तियों के लिए सभी सूचकांक हैश कर सकते हैं और जांच सकते हैं कि सरणी में प्रत्येक स्ट्रिंग के लिए प्रत्येक वर्ण के पास समान मान हैशेड है। लेकिन हैशिंग पार्ट को प्रीप्रोसेस करने के लिए हमें पहले सभी 26 पात्रों को हैश करने की आवश्यकता है। उसके आधार पर, हम उन्हें एक सरणी में संग्रहीत कर सकते हैं और इसे वापस कर सकते हैं।

कलन विधि

  1. एक HashMap बनाएँ पंक्तिबद्ध और एक सरणी परिणाम परिणामी तारों को संग्रहीत करने के लिए
  2. एक बूलियन चर को प्रारंभ करें same_row = सत्य तार पर जाँच चलाने के लिए
  3. सभी पात्रों को उनकी पंक्तियों को सुनाना
  4. सरणी में प्रत्येक स्ट्रिंग के लिए:
    • same_row = true सेट करें
    • हर किरदार के लिए chr सरणी में से शुरू दूसरा:
      • अगर rowId [chr] के बराबर नहीं है rowId [first_character]:
        • समान_रो = गलत सेट करें और अगली स्ट्रिंग पर जाएं
    • अगर वही_रो == सच:
      • इसे पुश करें परिणाम
  5. वापसी परिणाम

कीबोर्ड रो लेटकोड समाधान का कार्यान्वयन

C ++ प्रोग्राम

#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;
}

जावा प्रोग्राम

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

कीबोर्ड रो लेटकोड सॉल्यूशन की जटिलता विश्लेषण

समय जटिलता

पर) जैसा कि हम सरणी में हर स्ट्रिंग के हर चरित्र के माध्यम से पार करते हैं। N = सभी तारों की लंबाई का योग।

अंतरिक्ष जटिलता

O (1) के रूप में हम स्मृति की परवाह किए बिना स्मृति में लगातार जगह।