ການແກ້ໄຂຄີບອດ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ວຽກຄະນິດສາດ
ແຮກ string

ຖະແຫຼງການບັນຫາ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບ array ຂອງຊ່ອຍແນ່. ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາສາຍໃດໃນແຖວທີ່ໃຫ້ນັ້ນເປັນຂອງແຖວໃດ ໜຶ່ງ ຢູ່ໃນແຖວ QWERTY ແປ້ນພິມດັ່ງຮູບຂ້າງລຸ່ມນີ້:

ການແກ້ໄຂຄີບອດ Leetcode

ພວກເຮົາສົມມຸດວ່າອາເລປະກອບດ້ວຍສາຍອັກສອນຂອງພາສາອັງກິດ.

ຍົກຕົວຢ່າງ

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

ວິທີການ (Hashing)

ວິທີການແມ່ນງ່າຍດາຍ. ພວກເຮົາສາມາດສະແດງຕົວຊີ້ວັດທັງ ໝົດ ໃຫ້ແຖວຂອງພວກເຂົາແລະກວດເບິ່ງວ່າທຸກໆຕົວອັກສອນ ສຳ ລັບທຸກໆສາຍໃນແຖວມີມູນຄ່າເທົ່າກັນ. ແຕ່ພວກເຮົາ ຈຳ ເປັນຕ້ອງມີຕົວອັກສອນທັງ ໝົດ 26 ຕົວ ທຳ ອິດເພື່ອ ທຳ ການຜະລິດພາກສ່ວນທີ່ມີຄວາມຫຍຸ້ງຍາກ. ອີງໃສ່ສິ່ງນັ້ນ, ພວກເຮົາສາມາດເກັບຮັກສາພວກມັນໄວ້ເປັນແຖວແລະສົ່ງມັນຄືນ.

ລະບົບວິເຄາະ

  1. ສ້າງ HashMap rowId ແລະຂບວນການ ຜົນ ເພື່ອເກັບຮັກສາສາຍເຊືອກທີ່ໄດ້ຮັບ
  2. ເລີ່ມຕົ້ນຕົວແປ boolean same_row = ຈິງ ເພື່ອ ດຳ ເນີນການກວດເຊັກ
  3. ຮັດຕົວອັກສອນທັງ ໝົດ ໃສ່ແຖວຂອງພວກເຂົາ
  4. ສຳ ລັບທຸກໆເສັ້ນລວດໃນແຖວ:
    • ຕັ້ງຄ່າດຽວກັນ = ຖືກຕ້ອງ
    • ສຳ ລັບທຸກໆຕົວລະຄອນ ໃນຂບວນເລີ່ມຕົ້ນຈາກ ຄັ້ງທີສອງ:
      • ຖ້າ rowId [chr] ບໍ່ເທົ່າກັບ rowId [first_character]:
        • ຕັ້ງຄ່າດຽວກັນ = ບໍ່ຖືກຕ້ອງແລະເຕັ້ນໄປຫາສາຍຕໍ່ໄປ
    • ຖ້າດຽວກັນ = ຍົກ == ຄວາມຈິງ:
      • ຍູ້ມັນໄປ ຜົນ
  5. Return ຜົນ

ການຈັດຕັ້ງປະຕິບັດ 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;
}

Java Program

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

ການວິເຄາະຄວາມສັບສົນຂອງ Keyboard Row Leetcode Solution

ຄວາມສັບສົນເວລາ

ໂອ (N) ດັ່ງທີ່ພວກເຮົາໄດ້ຜ່ານລັກສະນະຂອງທຸກໆສາຍໃນແຖວ. N = sum of lengths of all the strings.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ດັ່ງທີ່ພວກເຮົາມີພື້ນທີ່ຄົງທີ່ຢູ່ໃນຄວາມຊົງ ຈຳ ໂດຍບໍ່ ຈຳ ແນກຄວາມຊົງ ຈຳ.