ស្វែងរកដំណោះស្រាយលក្ខណៈអក្សរឡាតកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ក្រុមហ៊ុន google ក្រុមហ៊ុន Microsoft TripAdvisor Uber
អារេ ហាសហាស។

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហានេះយើងត្រូវបានផ្តល់ឱ្យ អារេ of ខ្សែអក្សរ។ យើងត្រូវបោះពុម្ពបញ្ជីតួអក្សរទាំងអស់ដែលមាននៅគ្រប់ខ្សែអក្សរក្នុងជួរអារេ (បញ្ចូលលេខស្ទួន) ។ នោះគឺប្រសិនបើតួអក្សរលេចឡើង 2 ដងនៅគ្រប់ខ្សែអក្សរប៉ុន្តែមិនមែន 3 ដងទេយើងត្រូវមានវា 2 ដងនៅក្នុងលទ្ធផល។

ចំណាំថារាល់តួអក្សរទាំងអស់នៅក្នុងខ្សែអក្សរគឺជាអក្សរអង់គ្លេសតូចហើយខ្សែអក្សរមានប្រវែងអតិបរមា ១០០ ។

ឧទាហរណ៍

String_Array = {"bella" , "ciao" , "espanol"}
a
String_Array = {"qweerty" , "weerty" , "eerty"}
e e r t y

 

ស្វែងរកដំណោះស្រាយលក្ខណៈអក្សរឡាតកូដ

វិធីសាស្រ្ត (ហាស់ម៉ាស)

ដំបូងយើងអាចប្រើហេមស៍និយាយ ចំនួនចុងក្រោយ ដើម្បីទុកចំនួនតួអក្សរដែលមាននៅក្នុង ['a', 'z'] ដើម្បីរក្សាទុករបស់ពួកគេ អប្បបរមាជារឿងធម្មតា វត្តមាននៅក្នុងខ្សែអក្សរទាំងអស់។ ឧទាហរណ៍ប្រសិនបើយើងរកឃើញថាមាន ២ e គ្រប់ខ្សែអក្សរទាំងអស់ក្នុងអារេយើងរក្សាការរាប់របស់វាជា ២ ។ ដើម្បីទទួលបានលទ្ធផលនេះយើងទស្សនាតាមរយៈខ្សែអក្សរទាំងអស់ក្នុងអារេហើយបង្រួមអប្បបរមា ចំនួនចុងក្រោយ សម្រាប់រាល់តួអក្សរនៅក្នុង ['a', 'z'] ។ ទីបំផុតយើងរុញតួអក្សរមួយយោងទៅតាមការរាប់ចុងក្រោយរបស់វានៅក្នុងលទ្ធផលអារេ / បញ្ជីហើយប្រគល់វាមកវិញ។

ក្បួនដោះស្រាយ

  1. ចាប់ផ្តើមផែនទីហាស ចំនួនចុងក្រោយ ដើម្បីទុករូបរាងទូទៅអប្បបរមានៃរាល់តួអក្សរ
  2. សម្រាប់អក្សរអង់គ្លេសអក្សរតូចទាំងអស់៖
    • កំណត់របស់ពួកគេ ចំនួនចុងក្រោយ ដូច ០.១៥ ។
  3. សម្រាប់រាល់ខ្សែអក្សរ ពាក្យ នៅក្នុងអារេដែលបានផ្តល់ឱ្យ:
    • រក្សាទុកចំនួនតួអក្សរទាំងអស់នៅក្នុងផែនទីសញ្ញា រាប់
    • សម្រាប់រាល់អក្សរអង់គ្លេសអក្សរតូច c:
      • កំណត់: finalCount [គ] = អោយខ្ញុំ (ចំនួនចុងក្រោយ [គ] រាប់ [គ])
  4. ចាប់ផ្តើមបញ្ជី / អារេ លទ្ធផល ដើម្បីទុកអារេនៃតួអក្សរទូទៅ។
  5. សម្រាប់គ្រប់តួអក្សរ នៅក្នុងជួរ ['a', 'z']៖
    • បន្ថែមវាទៅក្នុងបញ្ជីឱ្យបានច្រើនដង ចំនួនចុងក្រោយ [គ]
  6. បោះពុម្ពលទ្ធផល

ការអនុវត្តនៃការស្វែងរកតួអក្សរទូទៅដំណោះស្រាយឡេឡេកូដ

កម្មវិធី C ++

#include <bits/stdc++.h>
using namespace std;

vector <string> commonChars(vector <string> A)
{
    unordered_map <char , int> finalCount;

    for(char c = 'a' ; c <= 'z' ; ++c)
        finalCount[c] = 100;

    unordered_map <char , int> count;

    for(string &word : A)
    {
        count.clear();
        for(char c : word)
            count[c]++;

        for(char c = 'a' ; c <= 'z' ; ++c)
            finalCount[c] = min(finalCount[c] , count[c]);
    }

    vector <string> result;

    string temp;

    int times;
    for(char c = 'a' ; c <= 'z' ; ++c)
    {
        times = finalCount[c];
        temp = c;
        while(times > 0)
        {
            result.push_back(temp);
            --times;
        }
    }
    return result;
}

int main()
{
    vector <string> A = {"qweerty" , "weerty" , "eerty"};
    vector <string> result = commonChars(A);
    if(result.empty())
        cout << "No common characters\n";
    else
    {
        for(string &s : result)
            cout << s << " ";
    }

    return 0;
}

កម្មវិធីចាវ៉ា

import java.util.*;
import java.lang.*;

class common_chars
{
    public static void main(String args[])
    {
        String[] A = {"qweerty" , "weerty" , "eerty"};
        List <String> result = commonChars(A);
        if(result.size() == 0)
            System.out.println("No common characters");
        else
        {
            for(String s : result)
                System.out.print(s + " ");
        }
    }

    static List <String> commonChars(String[] A)
    {
        HashMap <Character , Integer> finalCount = new HashMap<>();

        for(char c = 'a' ; c <= 'z' ; ++c)
            finalCount.put(c , 100);

        HashMap <Character , Integer> count = new HashMap<>();
        for(String word : A)
        {
            count.clear();
            for(char c : word.toCharArray())
                count.put(c , count.getOrDefault(c , 0) + 1);

            for(char c = 'a' ; c <= 'z' ; ++c)
                finalCount.put(c , Math.min(finalCount.get(c) , count.getOrDefault(c , 0)));
        }

        List <String> result = new ArrayList<>();

        int times;
        for(char c = 'a' ; c <= 'z' ; ++c)
        {
            times = finalCount.get(c);
            while(times > 0)
            {
                result.add(Character.toString(c));
                --times;
            }
        }
        return result;
    }
}
e e r t y

ការវិភាគភាពស្មុគស្មាញនៃការស្វែងរកលក្ខណៈទូទៅដំណោះស្រាយឡេឡេកូដ

ស្មុគស្មាញពេលវេលា

O (N) ដូចដែលយើងធ្វើតែមួយនៃខ្សែអក្សរទាំងអស់នៅក្នុងអារេដើម្បីធ្វើឱ្យទាន់សម័យចំនួនតួអក្សរ។ N = ផលបូកនៃប្រវែងនៃខ្សែនៅក្នុងអារេ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១) ដូចដែលយើងប្រើទំហំមេម៉ូរីថេរដើម្បីផ្ទុកចំនួនតួអក្សរ។