კლავიატურის რიგის Leetcode ამოხსნა


Რთული ტური Easy
ხშირად ეკითხებიან მათემატიკის სამუშაოები
ჰაშინგი სიმებიანი

პრობლემის განცხადება

ამ პრობლემის დროს ჩვენ გვეძლევა მასივი სიმების. უნდა ვიპოვოთ მოცემული მასივის რომელი სტრიქონები ეკუთვნის იგივე სტრიქონს QWERTY კლავიატურა, როგორც ნაჩვენებია ქვემოთ:

კლავიატურის რიგის Leetcode ამოხსნა

ჩვენ ჩავთვლით, რომ მასივი შეიცავს ინგლისური ასოების სტრიქონებს.

მაგალითი

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

მიდგომა (hashing)

მიდგომა საკმაოდ მარტივია. ჩვენ შეგვიძლია გავაშალოთ ყველა ინდექსები მათი რიგებისკენ და შეამოწმოთ, რომ მასივის ყველა სიმბოლოს ყველა სიმბოლოს აქვს იგივე მნიშვნელობა. პირველ რიგში, საჭიროა 26-ე სიმბოლოს ჰეშის მოპოვება, რათა ჰეშის ნაწილის წინასწარ გადამუშავება მოხდეს. ამის საფუძველზე, ჩვენ შეგვიძლია მათი მასივი შენახვა და დაბრუნება.

ალგორითმი

  1. შექმენით HashMap მწკრივი და მასივი შედეგად შედეგიანი სიმების შესანახად
  2. ლოგიკური ცვლადის ინიციალიზაცია იგივე_როლი = მართალია სტრიქონებზე შემოწმების გასაშვებად
  3. გაანადგურე ყველა სიმბოლო რიგებში
  4. მასივის ყველა სტრიქონისთვის:
    • მითითებული same_row = true
    • ყველა პერსონაჟისთვის chr მასივში იწყება მეორე:
      • თუ rowId [chr] ტოლი არ არის rowId [პირველი_ პერსონაჟი]:
        • მითითებული same_row = false და გადადით შემდეგ სტრიქონზე
    • თუ იგივე_როლა == მართალია:
      • უბიძგეთ მას შედეგად
  5. დაბრუნების შედეგად

Keyboard Row Leetcode Solution- ის განხორციელება

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

კლავიატურის რიგის Leetcode ამოხსნის სირთულის ანალიზი

დროის სირთულე

O (N) როგორც მასივის ყველა სტრიქონის ყველა პერსონაჟს გადავხედავთ. N = ყველა სტრიქონის სიგრძის ჯამი.

სივრცის სირთულე

O (1) როგორც მეხსიერების მუდმივი სივრცე, მეხსიერებისგან დამოუკიდებლად.