Βρείτε κοινούς χαρακτήρες Leetcode Solution


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα μήλο Bloomberg Google Microsoft Το TripAdvisor Uber
Παράταξη Hashing

Δήλωση προβλήματος

Σε αυτό το πρόβλημα, μας δίνεται ένα παράταξη of χορδές. Πρέπει να εκτυπώσουμε μια λίστα με όλους τους χαρακτήρες που εμφανίζονται σε κάθε συμβολοσειρά του πίνακα (περιλαμβάνονται διπλότυπα). Αυτό συμβαίνει εάν ένας χαρακτήρας εμφανίζεται 2 φορές σε κάθε συμβολοσειρά, αλλά όχι 3 φορές, πρέπει να έχουμε 2 φορές στο αποτέλεσμα.

Σημειώστε ότι κάθε χαρακτήρας στη συμβολοσειρά είναι πεζό γράμμα Αγγλικά και οι συμβολοσειρές έχουν μέγιστο μήκος 100.

Παράδειγμα

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

 

Βρείτε κοινούς χαρακτήρες Leetcode Solution

Πλησιάζω(HashMaps)

Μπορούμε πρώτα να χρησιμοποιήσουμε έναν κατακερματισμό, ας πούμε finalCount για να αποθηκεύσετε τον αριθμό των χαρακτήρων που κυμαίνονται σε ['a', 'z'] για να αποθηκεύσετε τους ελάχιστο κοινό παρουσία σε όλες τις χορδές. Για παράδειγμα, αν διαπιστώσουμε ότι υπάρχουν 2 's σε κάθε συμβολοσειρά στον πίνακα, διατηρούμε τον αριθμό του ως 2. Για να το επιτύχουμε αυτό, επισκέπτουμε κάθε συμβολοσειρά του πίνακα και ελαχιστοποιούμε το finalCount για κάθε χαρακτήρα στο ['a', 'z']. Τέλος, προωθούμε έναν χαρακτήρα σύμφωνα με τον τελικό του αριθμό σε έναν πίνακα αποτελεσμάτων / λίστα και τον επιστρέφουμε.

Αλγόριθμος

  1. Αρχικοποιήστε έναν κατακερματισμό χάρτη finalCount για να αποθηκεύσετε την ελάχιστη κοινή εμφάνιση κάθε χαρακτήρα
  2. Για κάθε πεζό γράμμα:
    • Ορίστε τους finalCount ως το 100.
  3. Για κάθε συμβολοσειρά λέξη στο δεδομένο πίνακα:
    • Αποθηκεύστε την καταμέτρηση κάθε χαρακτήρα σε έναν κατακερματισμό μετράνε
    • Για κάθε πεζό γράμμα Αγγλικά c:
      • Σειρά: finalCount [c] = πρακτικά (finalCount [c], count [c])
  4. Αρχικοποιήστε μια λίστα / πίνακα αποτέλεσμα για να αποθηκεύσετε τη σειρά κοινών χαρακτήρων.
  5. Για κάθε χαρακτήρα στην περιοχή ['a', 'z']:
    • Προσθέστε το στη λίστα όσες φορές finalCount [γ]
  6. Εκτυπώστε το αποτέλεσμα

Εφαρμογή της Εύρεση κοινών χαρακτήρων Leetcode Solution

Πρόγραμμα 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;
}

Πρόγραμμα Java

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

Ανάλυση πολυπλοκότητας εύρεσης κοινών χαρακτήρων Λύση κωδικού Leetcode

Χρόνος πολυπλοκότητας

ΕΠΙ) καθώς κάνουμε ένα μόνο πέρασμα κάθε συμβολοσειράς στον πίνακα για να ενημερώσουμε τον αριθμό των χαρακτήρων. N = Άθροισμα μήκους συμβολοσειρών στον πίνακα.

Διαστημική πολυπλοκότητα

Ο (1) καθώς χρησιμοποιούμε σταθερό χώρο μνήμης για να αποθηκεύουμε μετρήσεις χαρακτήρων.