Рішення клавіатури 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 = true запускати перевірки на рядки
  3. Хеш усіх символів до їх рядків
  4. Для кожного рядка str у масиві:
    • встановити same_row = true
    • Для кожного персонажа хр у масиві, починаючи з друге:
      • Якщо rowId [chr] не дорівнює rowId [first_character]:
        • встановити same_row = false і перейти до наступного рядка
    • Якщо same_row == true:
      • Натисніть на результат
  5. Повертати результат

Впровадження рішення клавіатури Leetcode

Програма С ++

#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;
}

Програма Java

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), оскільки ми постійно зберігаємо простір у пам'яті незалежно від пам’яті.