Keyboard Row Leetcode Solution


سطح دشواری ساده
اغلب در Mathworks
هشی کردن رشته

بیان مسأله

در این مشکل ، به ما داده می شود صف رشته ها باید پیدا کنیم که کدام رشته های آرایه داده شده مربوط به همان ردیف های موجود در آرایه هستند QWERTY صفحه کلید همانطور که در زیر نشان داده شده است:

Keyboard Row Leetcode Solution

ما فرض می کنیم که آرایه شامل رشته هایی از حروف انگلیسی است.

مثال

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

رویکرد (هش کردن)

این روش کاملاً ساده است. ما می توانیم تمام شاخص ها را به ردیف های آنها هش کنیم و بررسی کنیم که هر کاراکتر برای هر رشته در آرایه دارای همان ارزش هدیه شده برای آن است. اما برای اینکه از قبل قسمت هش را پردازش کنیم ابتدا باید برای همه 26 کاراکتر هش کنیم. بر این اساس ، می توانیم آنها را در یک آرایه ذخیره کرده و برگردانیم.

الگوریتم

  1. یک HashMap ایجاد کنید rowId و یک آرایه نتیجه برای ذخیره رشته های حاصل
  2. یک متغیر بولی را ابتدا شروع کنید same_row = درست است برای اجرای چک در رشته ها
  3. همه کاراکترها را در ردیف خود قرار دهید
  4. برای هر رشته در آرایه:
    • تنظیم same_row = درست است
    • برای هر شخصیتی CHR در آرایه شروع شده از دومین:
      • اگر rowId [chr] برابر نیست rowId [شخصیت_اولین]:
        • set same_row = false را انتخاب کرده و به رشته بعدی بروید
    • اگر same_row == درست باشد:
      • فشار آن را به نتیجه
  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

تجزیه و تحلیل پیچیدگی صفحه کلید صفحه کلید حل محلول

پیچیدگی زمان

بر) همانطور که از هر کاراکتر از هر رشته در آرایه عبور می کنیم. N = مجموع طول همه رشته ها.

پیچیدگی فضا

O (1) همانطور که فضای حافظه را بدون توجه به حافظه ثابت نگه می داریم.