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


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

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

இந்த சிக்கலில், எங்களுக்கு ஒரு வழங்கப்படுகிறது வரிசை of சரங்களை. வரிசையில் உள்ள ஒவ்வொரு சரத்திலும் தோன்றும் அனைத்து எழுத்துகளின் பட்டியலையும் அச்சிட வேண்டும் (நகல்கள் சேர்க்கப்பட்டுள்ளன). அதாவது, ஒவ்வொரு சரத்திலும் ஒரு எழுத்து 2 முறை தோன்றினாலும், 3 முறை அல்ல, அதன் விளைவாக 2 முறை இருக்க வேண்டும்.

சரத்தின் ஒவ்வொரு எழுத்தும் ஒரு சிறிய எழுத்து ஆங்கில எழுத்து மற்றும் சரங்களின் அதிகபட்ச நீளம் 100 என்பதை நினைவில் கொள்க.

உதாரணமாக

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

 

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

அணுகுமுறை (ஹாஷ்மேப்ஸ்)

நாம் முதலில் ஒரு ஹாஷ்மாப்பைப் பயன்படுத்தலாம், சொல்லுங்கள் இறுதி எண்ணிக்கை ['a', 'z'] வரையிலான எழுத்துக்களின் எண்ணிக்கையை சேமிக்க குறைந்தபட்ச பொதுவானது அனைத்து சரங்களிலும் இருப்பு. எடுத்துக்காட்டாக, வரிசையில் உள்ள ஒவ்வொரு சரத்திலும் 2 'e கள் இருப்பதைக் கண்டால், அதன் எண்ணிக்கையை 2 ஆக பராமரிக்கிறோம். இதை அடைய, வரிசையில் உள்ள ஒவ்வொரு சரம் வழியாகவும் சென்று குறைக்கிறோம் இறுதி எண்ணிக்கை ['a', 'z'] இல் உள்ள ஒவ்வொரு எழுத்துக்கும். இறுதியாக, ஒரு எழுத்துக்குறி அதன் இறுதி எண்ணிக்கையின்படி ஒரு முடிவு வரிசை / பட்டியலில் தள்ளி அதை திருப்பித் தருகிறோம்.

அல்காரிதம்

  1. ஹாஷ் வரைபடத்தைத் தொடங்கவும் இறுதி எண்ணிக்கை ஒவ்வொரு கதாபாத்திரத்தின் குறைந்தபட்ச பொதுவான தோற்றத்தை சேமிக்க
  2. ஒவ்வொரு சிறிய எழுத்துக்களுக்கும்:
    • அவற்றின் அமைக்கவும் இறுதி எண்ணிக்கை 100 ஆக.
  3. ஒவ்வொரு சரத்திற்கும் வார்த்தை கொடுக்கப்பட்ட வரிசையில்:
    • ஒவ்வொரு எழுத்தின் எண்ணிக்கையையும் ஹாஷ் வரைபடத்தில் சேமிக்கவும் எண்ண
    • ஒவ்வொரு சிறிய எழுத்துக்கும் ஆங்கில கடிதம் c:
      • அமை: இறுதி எண்ணிக்கை [c] = நிமிடம் (இறுதி எண்ணிக்கை [c], எண்ணிக்கை [c])
  4. பட்டியல் / வரிசையைத் தொடங்கவும் விளைவாக பொதுவான எழுத்துகளின் வரிசையை சேமிக்க.
  5. ஒவ்வொரு கதாபாத்திரத்திற்கும் ['a', 'z'] வரம்பில்:
    • அதை பட்டியலில் பல முறை சேர்க்கவும் இறுதி எண்ணிக்கை [c]
  6. முடிவை அச்சிடுங்கள்

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

சி ++ திட்டம்

#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

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

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

ஓ (என்) எழுத்துகளின் எண்ணிக்கையைப் புதுப்பிக்க வரிசையில் உள்ள ஒவ்வொரு சரத்தின் ஒற்றை பாஸை நாங்கள் செய்கிறோம். N = வரிசையில் உள்ள சரங்களின் நீளங்களின் தொகை.

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

ஓ (1) எழுத்துகளின் எண்ணிக்கையை சேமிக்க நிலையான நினைவக இடத்தைப் பயன்படுத்துகிறோம்.