सामान्य वर्ण लेटकोड समाधान खोजें


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना सेब ब्लूमबर्ग गूगल माइक्रोसॉफ्ट TripAdvisor Uber
ऐरे hashing

समस्या का विवरण

इस समस्या में, हमें एक दिया जाता है सरणी 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])
  4. सूची / एरे को आरम्भ करें परिणाम आम पात्रों की सरणी को संग्रहीत करने के लिए।
  5. हर किरदार के लिए सीमा में ['a', 'z']:
    • इसे सूची में जितनी बार जोड़ो फ़ाइनलकाउंट [c]
  6. परिणाम प्रिंट करें

सामान्य वर्ण Leetcode समाधान खोजें का कार्यान्वयन

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 = सरणी में तार की लंबाई का योग।

अंतरिक्ष जटिलता

ओ (1) जैसा कि हम वर्णों की गिनती को संग्रहीत करने के लिए निरंतर मेमोरी स्पेस का उपयोग करते हैं।