కీబోర్డ్ వరుస లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది గణితాలు
హ్యాషింగ్ స్ట్రింగ్

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు ఒక ఇవ్వబడుతుంది అమరిక తీగలను. ఇచ్చిన శ్రేణిలోని ఏ తీగలను ఏ వరుసలోనైనా కనుగొనాలి QWERTY కీబోర్డ్ క్రింద చూపిన విధంగా:

కీబోర్డ్ వరుస లీట్‌కోడ్ పరిష్కారం

శ్రేణిలో ఆంగ్ల అక్షరాల తీగలను కలిగి ఉందని మేము అనుకుంటాము.

ఉదాహరణ

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

అప్రోచ్ (హాషింగ్)

విధానం చాలా సూటిగా ఉంటుంది. మేము అన్ని సూచికలను వాటి వరుసలకు హాష్ చేయవచ్చు మరియు శ్రేణిలోని ప్రతి స్ట్రింగ్‌కు ప్రతి అక్షరం దానికి సమానమైన విలువను కలిగి ఉందో లేదో తనిఖీ చేయవచ్చు. కానీ హాషింగ్ భాగాన్ని ముందస్తుగా ప్రాసెస్ చేయడానికి మనం మొదట మొత్తం 26 అక్షరాల కోసం హాష్ చేయాలి. దాని ఆధారంగా, మేము వాటిని శ్రేణిలో నిల్వ చేసి తిరిగి ఇవ్వవచ్చు.

అల్గారిథం

  1. హాష్ మ్యాప్ సృష్టించండి వరుస ఐడి మరియు శ్రేణి ఫలితంగా ఫలిత తీగలను నిల్వ చేయడానికి
  2. బూలియన్ వేరియబుల్ ప్రారంభించండి same_row = నిజం తీగలపై తనిఖీలను అమలు చేయడానికి
  3. అన్ని అక్షరాలను వారి వరుసలకు హాష్ చేయండి
  4. శ్రేణిలోని ప్రతి స్ట్రింగ్ కోసం:
    • set_row = true ని సెట్ చేయండి
    • ప్రతి పాత్రకు chr నుండి ప్రారంభమయ్యే శ్రేణిలో రెండవ:
      • అయితే rowId [chr] సమానం కాదు rowId [first_character]:
        • same_row = false అని సెట్ చేసి, తదుపరి స్ట్రింగ్‌కు వెళ్లండి
    • అదే_రో == నిజమైతే:
      • దానికి నెట్టండి ఫలితంగా
  5. రిటర్న్ ఫలితంగా

కీబోర్డ్ రో లీట్‌కోడ్ పరిష్కారం అమలు

సి ++ ప్రోగ్రామ్

#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) మెమరీతో సంబంధం లేకుండా మెమరీలో స్థిరమైన స్థలం.