حل Leetcode الصف لوحة المفاتيح


مستوى الصعوبة سهل
كثيرا ما يطلب في ماثووركس
تجزئة خيط

المشكلة بيان

في هذه المشكلة ، حصلنا على مجموعة من السلاسل. نحتاج إلى إيجاد السلاسل الموجودة في المصفوفة المحددة التي تنتمي إلى أي صف واحد في QWERTY لوحة المفاتيح كما هو موضح أدناه:

حل Leetcode الصف لوحة المفاتيح

نفترض أن المصفوفة تحتوي على سلاسل من الأحرف الإنجليزية.

مثال

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 = صحيح
    • لكل شخصية مركز حقوق الإنسان في المصفوفة بدءًا من ثانيا:
      • إذا كان RowId [chr] لا يساوي معرّف الصف [الحرف_الأول]:
        • اضبط same_row = false وانتقل إلى السلسلة التالية
    • إذا كان same_row == صحيحًا:
      • ادفعها إلى نتيجة
  5. الإرجاع نتيجة

تنفيذ حل Leetcode الصف لوحة المفاتيح

برنامج 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

تعقيد الوقت

على) بينما نتخطى كل حرف من كل سلسلة في المصفوفة. N = مجموع أطوال كل السلاسل.

تعقيد الفضاء

O (1) لأننا نثبّت مساحة في الذاكرة بغض النظر عن الذاكرة.