பொதுவான எழுத்துக்கள் லீட்கோட் தீர்வைக் கண்டறியவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் கிழித்து
அணி ஹேஷிங்

சிக்கல் அறிக்கை

இந்த சிக்கலில், எங்களுக்கு ஒரு பட்டியல் வழங்கப்படுகிறது சரம். எல்லா சரங்களிலும் பொதுவான எழுத்துக்களை நாம் கண்டுபிடிக்க வேண்டும். ஒரு எழுத்து அனைத்து சரங்களிலும் பல முறை இருந்தால், நாம் பாத்திரத்தை பல முறை வெளியிட வேண்டும்.
எங்களிடம் சரங்களின் வரிசை உள்ளது என்று வைத்துக்கொள்வோம்
[“பெல்லா”, ”லேபிள்”, “ரோலர்”]
'இ' எழுத்து அனைத்து சரங்களிலும் ஒரு முறை இருப்பதையும், எல்லா சரங்களிலும் எல் இரண்டு முறை இருப்பதையும் நாம் காணலாம். வேறு எந்த கதாபாத்திரமும் பொதுவானதல்ல.
எனவே, எங்கள் வெளியீட்டு பட்டியலில், 'e' எழுத்து ஒரு முறை இருக்கும், மற்றும் 'l' எழுத்து இரண்டு முறை இருக்கும்.

உதாரணமாக

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

அணுகுமுறை

இங்கே அனைத்து சரங்களிலும் அஸ் எழுத்துக்களின் பொதுவான அதிர்வெண்ணைக் கண்டுபிடிக்க வேண்டும் என்பதைக் காணலாம்.
ஒவ்வொரு சரத்திற்கும் நாம் அளவு 26 இன் எண்ணிக்கையை உருவாக்கலாம், இது az எழுத்துக்களின் அதிர்வெண் கொண்டது. குறியீட்டு 0 இல் அந்த சரத்தில் 'a' எண்ணும், குறியீட்டு 1 இல் 'b' எண்ணிக்கையும் இருக்கும்.
இப்போது a முதல் z வரையிலான ஒவ்வொரு எழுத்துக்கும், மேலே உருவாக்கப்பட்ட எந்த வரிசைகளிலும் இருக்கக்கூடிய குறைந்தபட்ச எண்ணிக்கையை நாம் கண்டுபிடிக்க வேண்டும். நாங்கள் இதைச் செய்கிறோம், ஏனென்றால் எல்லா சரங்களிலும் ஒரு பாத்திரத்தின் குறைந்தபட்ச இருப்பை நாங்கள் விரும்புகிறோம். வேறு வார்த்தைகளில் கூறுவதானால், ஒவ்வொரு சரத்திலிருந்து பொதுவான எழுத்துக்களை மட்டுமே எடுத்துக்கொள்கிறோம்.

 

பொதுவான எழுத்துக்கள் லீட்கோட் தீர்வைக் கண்டறியவும்

எனவே, நாம் முதலில் ஒரு பதிலை உருவாக்குவோம் வரிசை அளவு 26 இன் அனைத்து குறியீடுகளும் அதிகபட்ச மதிப்பில் அமைக்கப்பட்டுள்ளன.
பின்னர், சரங்களின் வரிசையை இடமிருந்து வலமாக பயணிப்போம். ஒவ்வொரு அடியிலும், தற்போதைய சரத்திற்கான எண்ணிக்கை வரிசையை உருவாக்குவோம். தற்போது உருவாக்கப்பட்ட வரிசையை ans வரிசையுடன் ஒப்பிடுவோம்.
எல்லாவற்றிலும் குறைந்தபட்சம் நாங்கள் ஆர்வமாக இருப்பதால், தற்போதைய வரிசையில் உள்ள ஒவ்வொரு குறியீடும் அந்த குறியீட்டில் உள்ள அன்ஸ் வரிசையின் மதிப்பை விட சிறியதாக இருந்தால் மட்டுமே மாற்றப்படும்.
அதாவது பதில் [i]

கொடுக்கப்பட்ட பட்டியலின் அனைத்து சரங்களையும் நாம் கடந்து சென்ற பிறகு, எழுத்துக்களின் பட்டியலை உருவாக்க எங்கள் பதில் வரிசையைப் பயன்படுத்துவோம். பதில் வரிசையில், குறியீட்டு 0 இல் உள்ள மதிப்பு 'a' எழுத்தின் எண்ணிக்கையையும், குறியீட்டு 1 இல் உள்ள மதிப்பு குறியீட்டு 'b' மற்றும் பலவற்றையும் காட்டுகிறது.
எனவே, இந்த வழியில் ஒவ்வொரு எழுத்தின் எண்ணிக்கையையும் a முதல் z வரை பயன்படுத்துவதன் மூலம் எங்கள் வெளியீட்டு வரிசைகளை உருவாக்குவோம்.

நடைமுறைப்படுத்தல்

பொதுவான எழுத்துக்களைக் கண்டுபிடிப்பதற்கான சி ++ நிரல் லீட்கோட் தீர்வு

#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

பொதுவான எழுத்துக்களைக் கண்டுபிடிப்பதற்கான சிக்கலான பகுப்பாய்வு லீட்கோட் தீர்வு

நேர சிக்கலானது

ஓ (ந): n என்பது அனைத்து சரங்களின் நீளத்தின் கூட்டுத்தொகையாகும்.

விண்வெளி சிக்கலானது 

ஓ (1): இரண்டு வரிசைகள் ans மற்றும் temp, ஒவ்வொன்றும் 26 அளவு பயன்படுத்தப்படுகிறது. இது நிலையான அளவு நினைவகத்தைத் தவிர வேறில்லை. இதனால் விண்வெளி சிக்கலானது O (1) ஆகும்.