সাধারণ অক্ষরগুলি লেটকোড সমাধান সন্ধান করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ গুগল মাইক্রোসফট দাবি উবার
বিন্যাস হ্যাশ

সমস্যা বিবৃতি

এই সমস্যায়, আমাদের একটি দেওয়া হয় বিন্যাস of স্ট্রিং। আমাদের অ্যারেতে প্রতিটি স্ট্রিংয়ে উপস্থিত সমস্ত অক্ষরের একটি তালিকা মুদ্রণ করতে হবে (নকল অন্তর্ভুক্ত)। এটি হ'ল যদি কোনও অক্ষর প্রতিটি স্ট্রিংয়ে 2 বার উপস্থিত হয়, তবে 3 বার নয়, ফলস্বরূপ আমাদের এটির 2 বার থাকা দরকার।

নোট করুন যে স্ট্রিংয়ের প্রতিটি অক্ষর হ'ল একটি ছোট অক্ষরের ইংরেজি বর্ণ এবং স্ট্রিংয়ের সর্বাধিক দৈর্ঘ্য 100 থাকে।

উদাহরণ

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

 

সাধারণ অক্ষরগুলি লেটকোড সমাধান সন্ধান করুন

পন্থা (হ্যাশম্যাপস)

আমরা প্রথমে একটি হ্যাশম্যাপ ব্যবহার করতে পারি, বলুন ফাইনালকাউন্ট ['a', 'z'] এর মধ্যে অক্ষরের সংখ্যাগুলি সংরক্ষণ করতে their সর্বনিম্ন সাধারণ সমস্ত স্ট্রিং উপস্থিতি। উদাহরণস্বরূপ, যদি আমরা সন্ধান করি যে অ্যারেতে প্রতিটি স্ট্রিংয়ে 2'র ই থাকে তবে আমরা এর গণনা 2 হিসাবে বজায় রাখি, এটি অর্জনের জন্য, আমরা অ্যারেতে প্রতিটি স্ট্রিং ঘুরে দেখি এবং ফাইনালকাউন্ট ['a', 'z'] এর প্রতিটি চরিত্রের জন্য। পরিশেষে, আমরা একটি ফলাফলের অ্যারে / তালিকায় একটি চরিত্রের চূড়ান্ত গণনা অনুসারে চাপি এবং এটি ফিরিয়ে আনি।

অ্যালগরিদম

  1. একটি হ্যাশ মানচিত্র শুরু করুন ফাইনালকাউন্ট প্রতিটি চরিত্রের সর্বনিম্ন সাধারণ উপস্থিতি সঞ্চয় করতে
  2. প্রতিটি ছোট ক্ষেত্রে ইংরেজি অক্ষরের জন্য:
    • তাদের সেট করুন ফাইনালকাউন্ট 100 হিসাবে।
  3. প্রতিটি স্ট্রিং জন্য শব্দ প্রদত্ত অ্যারে:
    • হ্যাশ মানচিত্রে প্রতিটি চরিত্রের গণনা সঞ্চয় করুন গণনা
    • প্রতিটি ছোট ক্ষেত্রে ইংরেজি অক্ষর c:
      • সেট করুন: ফাইনালকাউন্ট [সি] = মিনিট (চূড়ান্ত হিসাব [সি], গণনা [সি])
  4. একটি তালিকা / অ্যারে শুরু করুন ফল সাধারণ অক্ষরের অ্যারে সঞ্চয় করতে।
  5. প্রতিটি চরিত্রের জন্য ['a', 'z'] পরিসীমাটিতে:
    • এটিকে যতবার তালিকাতে যুক্ত করুন চূড়ান্ত হিসাব [সি]
  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 অ্যারেতে দৈর্ঘ্যের স্ট্রিংয়ের যোগফল।

স্পেস জটিলতা ity

ও (1) যেহেতু আমরা অক্ষরের সংখ্যা সঞ্চয় করতে ধ্রুবক মেমরি স্পেস ব্যবহার করি।