راه حل کد Leet برای شخصیت های مشترک پیدا کنید


سطح دشواری ساده
اغلب در خشت آمازون سیب بلومبرگ گوگل مایکروسافت مشاورین حال بارگذاری
صف هشی کردن

بیان مسأله

در این مشکل ، به ما داده می شود صف of رشته های. ما باید لیستی از همه نویسه هایی را که در هر رشته از آرایه ظاهر می شوند چاپ کنیم (نسخه های کپی شده). این در صورتی است که یک کاراکتر 2 بار در هر رشته ظاهر می شود ، اما 3 بار نیست ، ما باید آن را 2 بار در نتیجه داشته باشیم.

توجه داشته باشید که هر کاراکتر در این رشته یک حرف کوچک انگلیسی است و طول رشته ها حداکثر 100 است.

مثال

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

 

راه حل کد Leet برای شخصیت های مشترک پیدا کنید

رویکرد(HashMaps)

ابتدا می توانیم از یک هاشماپ استفاده کنیم حساب نهایی برای ذخیره تعداد کاراکترهای موجود در ['a'، 'z'] برای ذخیره آنها حداقل مشترک حضور در همه رشته ها. به عنوان مثال ، اگر متوجه شویم که در هر رشته از آرایه 2 'e وجود دارد ، تعداد آن را 2 حفظ می کنیم. برای رسیدن به این هدف ، از هر رشته آرایه بازدید می کنیم و مقدار آن را به حداقل می رسانیم. حساب نهایی برای هر شخصیت در ['a'، 'z']. در آخر ، ما یک کاراکتر را با توجه به تعداد نهایی آن در یک آرایه / لیست فشار می دهیم و آن را برمی گردانیم.

الگوریتم

  1. شروع یک نقشه هش حساب نهایی برای ذخیره حداقل ظاهر مشترک هر شخصیت
  2. برای هر حرف کوچک انگلیسی:
    • آنها را تنظیم کنید حساب نهایی به عنوان 100.
  3. برای هر رشته کلمه در آرایه داده شده:
    • تعداد هر کاراکتر را در یک نقشه هش ذخیره کنید تعداد دفعات مشاهده
    • برای هر حرف کوچک انگلیسی c:
      • تنظیم: تعداد نهایی [c] = دقیقه (finalCount [c] ، تعداد [c])
  4. لیست / آرایه را آغاز کنید نتیجه برای ذخیره آرایه شخصیت های مشترک
  5. برای هر شخصیتی در محدوده ['a'، 'z']:
    • هر چند بار آن را به لیست اضافه کنید finalCount [c]
  6. نتیجه را چاپ کنید

پیاده سازی راه حل کد Leet برای پیدا کردن شخصیت های مشترک

برنامه 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

تجزیه و تحلیل پیچیدگی برای پیدا کردن شخصیت های مشترک راه حل کد

پیچیدگی زمان

بر) همانطور که برای به روزرسانی تعداد کاراکترها از هر رشته در آرایه یک گذرگاه واحد انجام می دهیم. N = مجموع طول رشته ها در آرایه.

پیچیدگی فضا

O (1) همانطور که ما از فضای حافظه ثابت برای ذخیره تعداد کاراکترها استفاده می کنیم.