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


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon Uber
អារេ ហាសហាស។

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

នៅក្នុងបញ្ហានេះយើងត្រូវបានផ្តល់បញ្ជី ខ្សែអក្សរ។ យើងត្រូវរកឱ្យឃើញនូវតួអក្សរដែលមានលក្ខណៈទូទៅនៅក្នុងខ្សែរទាំងអស់។ ប្រសិនបើតួអក្សរមានវត្តមាននៅក្នុងខ្សែរទាំងអស់ក្នុងច្រើនដងនោះយើងត្រូវបញ្ចេញតួអក្សរអោយច្រើនដង។
ឧបមាថាយើងមានខ្សែអក្សរជាច្រើន
[“ ប៊ីឡា”,” ស្លាក”,“ រំកិល”]
យើងអាចឃើញថាតួអក្សរ 'e' មានវត្តមានម្តងក្នុងខ្សែទាំងអស់ខ្ញុំមានវត្តមានពីរដងនៅក្នុងខ្សែទាំងអស់។ មិនមានចរិតផ្សេងទៀតដែលជារឿងធម្មតាទេ។
ដូច្នេះនៅក្នុងបញ្ជីលទ្ធផលរបស់យើងតួអក្សរ 'e' នឹងមានម្តងហើយតួអក្សរ 'l' នឹងមានវត្តមានពីរដង។

ឧទាហរណ៍

["bella","label","roller"]
["e","l","l"]
["cool","lock","cook"]
["c","o"]

វិធីសាស្រ្ត

យើងអាចឃើញថាយើងត្រូវតែស្វែងយល់អំពីប្រេកង់ទូទៅនៃតួអក្សរ az នៅក្នុងខ្សែអក្សរទាំងអស់នៅទីនេះ។
សម្រាប់រាល់ខ្សែអក្សរយើងអាចបង្កើតជួររាប់នៃទំហំ ២៦ ដែលមានប្រេកង់តួអក្សរ az ។ លិបិក្រម ០ នឹងមានចំនួន“ a” នៅក្នុងខ្សែនោះហើយលិបិក្រម ១ មានចំនួន“ b” និងផ្សេងទៀត
ឥឡូវសម្រាប់តួអក្សរនីមួយៗពី a ដល់ Z យើងត្រូវរកចំនួនអប្បបរមាដែលអាចមាននៅក្នុងអារេណាមួយដែលបានបង្កើតខាងលើ។ យើងកំពុងធ្វើនេះពីព្រោះយើងចាប់អារម្មណ៍នឹងវត្តមានអប្បបរមានៃចរិតមួយនៅក្នុងខ្សែទាំងអស់។ និយាយម៉្យាងទៀតយើងកំពុងយកតែតួអក្សរធម្មតាពីខ្សែនីមួយៗ។

 

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

ដូច្នេះដំបូងយើងនឹងបង្កើតចម្លើយ អារេ នៃទំហំ ២៦ ដែលមានសន្ទស្សន៍ទាំងអស់ត្រូវបានកំណត់ក្នុងតម្លៃអតិបរមា។
បន្ទាប់មកយើងនឹងឆ្លងកាត់ជួរនៃខ្សែពីឆ្វេងទៅស្តាំ។ ក្នុងជំហាននីមួយៗយើងនឹងបង្កើតអារេរាប់សម្រាប់ខ្សែបច្ចុប្បន្ន។ បន្ទាប់មកយើងនឹងប្រៀបធៀបអារេដែលបានបង្កើតបច្ចុប្បន្នជាមួយអារេអារេ។
ពីព្រោះយើងចាប់អារម្មណ៍យ៉ាងតិចបំផុតដូច្នេះរាល់សន្ទស្សន៍នៃអារេ Ans នឹងត្រូវបានកែប្រែប្រសិនបើតម្លៃនៅក្នុងអារេបច្ចុប្បន្នតូចជាងតម្លៃរបស់អារេនៅសន្ទស្សន៍នោះ។
ឧទាហរណ៍ប្រសិនបើឆ្លើយ [ខ្ញុំ]

បន្ទាប់ពីយើងបានឆ្លងកាត់ខ្សែអក្សរទាំងអស់នៃបញ្ជីដែលបានផ្តល់រួចហើយយើងនឹងប្រើអារេរបស់យើងដើម្បីបង្កើតបញ្ជីតួអក្សរ។ នៅក្នុងចម្លើយចម្លើយតម្លៃនៅសន្ទស្សន៍ ០ បង្ហាញចំនួនតួអក្សរ 'a', តម្លៃនៅសន្ទស្សន៍ ១ បង្ហាញពីចំនួនសន្ទស្សន៍ 'b' និងផ្សេងទៀត។
ដូច្នេះតាមវិធីនេះយើងនឹងបង្កើតតួអក្សររបស់យើងដោយប្រើចំនួនតួអក្សរនីមួយៗពី a ដល់ z ។

ការអនុវត្តន៍

កម្មវិធី C ++ សម្រាប់ស្វែងរកលក្ខណៈទូទៅឡេឡេសកូដសូលូសិន

#include <iostream>
#include <vector>
using namespace std;
vector<string> commonChars(vector<string>& A) {
        int ans[26];
        int temp[26];
        fill(ans,ans+26,100);
        for(string str:A){
            fill(temp, temp+26,0);
            for(int i=0;i<str.size();i++){
                temp[str[i]-'a']++;
            }
            for(int i=0;i<26;i++){
                ans[i]=min(ans[i],temp[i]);
            }
        }
        vector<string>ansChars;
        for(int i=0;i<26;i++){
            for(int j=0;j<ans[i];j++){
                char ch=((char)(i+'a'));
                string s(1, ch); //convert char ch to string s
                ansChars.push_back(s);
            }
        }
        return ansChars;
    }
int main()
{
    vector<string>A{"bella","label","roller"};
    vector<string>ans = commonChars(A);
    for(string str:ans){
        cout<<str<<" ";
    }
    cout<<endl;
}
e l l

កម្មវិធីចាវ៉ាសម្រាប់ស្វែងរកលក្ខណៈទូទៅនៃឡេឡេសកូដដំណោះស្រាយ

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

class Solution
{  
    public static void main(String args[])
    {
        String[]A={"bella","label","roller"};
        List<String>ans=commonChars(A);
        for(String str:ans){
            System.out.print(str+" ");
        }
        System.out.println();
    }
    public static List<String> commonChars(String[] A) {
        int[]ans=new int[26];
        int[]temp=new int[26];
        Arrays.fill(ans,Integer.MAX_VALUE);
        for(String str:A){
            Arrays.fill(temp,0);
            for(int i=0;i<str.length();i++){
                temp[str.charAt(i)-'a']++;
            }
            for(int i=0;i<26;i++){
                ans[i]=Math.min(ans[i],temp[i]);
            }
        }
        List<String>ansChars=new ArrayList<String>();
        for(int i=0;i<ans.length;i++){
            for(int j=0;j<ans[i];j++){
                ansChars.add((char)(i+'a')+"");
            }
        }
        return ansChars;
    }
}
e l l

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

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

O (n)៖ ដែល n ជាផលបូកនៃប្រវែងខ្សែអក្សរទាំងអស់។

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

O (១)៖ អារេពីរនិងបណ្ដោយពីរដែលមានទំហំ ២៦ ត្រូវបានប្រើ។ ដែលមិនមានអ្វីក្រៅពីការចងចាំទំហំថេរ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺ O (26) ។