কীবোর্ড সারি লেটকোড সমাধান  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় গণিত
আলগোরিদিম আইনসংগ্রহ হ্যাশ সাক্ষাত্কার সাক্ষাৎকারের প্রস্তুতি লেটকোড LeetCodeSolutions স্ট্রিং

সমস্যা বিবৃতি  

এই সমস্যায়, আমাদের একটি দেওয়া হয় বিন্যাস স্ট্রিং। আমাদের প্রদত্ত অ্যারেতে কোন স্ট্রিংগুলি কোনও একই সারির সাথে সম্পর্কিত তা খুঁজে বের করতে হবে কোয়ার্টি কীবোর্ড নীচে প্রদর্শিত হিসাবে:

কীবোর্ড সারি লেটকোড সমাধানপিন

আমরা ধরে নিই যে অ্যারেতে ইংরেজি বর্ণগুলির স্ট্রিং রয়েছে।

উদাহরণ

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

পদ্ধতির (হ্যাশিং)  

পদ্ধতিটি বেশ সোজা। আমরা সমস্ত সূচকগুলি তাদের সারিগুলিতে হ্যাশ করতে পারি এবং এটি পরীক্ষা করতে পারি যে অ্যারের প্রতিটি স্ট্রিংয়ের প্রতিটি অক্ষরের সাথে একই মান রয়েছে। তবে হ্যাশিং অংশটি প্রিপ্রোস করার জন্য আমাদের প্রথমে 26 টি অক্ষরের জন্য হ্যাশ দরকার। তার উপর ভিত্তি করে, আমরা এগুলিকে একটি অ্যারেতে সঞ্চয় করতে এবং এটি ফিরিয়ে দিতে পারি।

অ্যালগরিদম

  1. একটি হ্যাশম্যাপ তৈরি করুন সারি এবং একটি অ্যারে ফল ফলস্বরূপ স্ট্রিং সঞ্চয় করতে
  2. বুলিয়ান চলক শুরু করুন একই_আরো = সত্য স্ট্রিংগুলিতে চেক চালাতে
  3. সমস্ত অক্ষর তাদের সারি হ্যাশ
  4. অ্যারের প্রতিটি স্ট্রিংয়ের জন্য:
    • সেট একই_আরো = সত্য
    • প্রতিটি চরিত্রের জন্য chr, অ্যারে থেকে শুরু দ্বিতীয়:
      • যদি সারিবদ্ধ [chr] সমান নয় সারিআইড [প্রথম_চারণকারী]:
        • একই_রো = মিথ্যা সেট করুন এবং পরবর্তী স্ট্রিংয়ে লাফ দিন
    • যদি একই_আর == সত্য:
      • এটি পুশ করুন ফল
  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 = সমস্ত স্ট্রিংয়ের দৈর্ঘ্যের যোগফল।

আরো দেখুন
রোমান লেটকোড সমাধানের পূর্ণসংখ্যা

স্পেস জটিলতা ity

ও (1) মেমরি নির্বিশেষে আমরা স্মৃতিতে স্থির হিসাবে থাকি।

1