Ordene una array de strings según la frecuencia de buenas palabras en ellas

Dado un conjunto de reseñas de productos ( R ) de diferentes clientes y una string S que contiene buenas palabras separadas por un _ , la tarea es ordenar las reseñas en orden decreciente de su valor de bondad.
El valor de bondad se define por el número de buenas palabras presentes en esa reseña.

Ejemplos:

Entrada: S = “geeks_for_geeks_is_great”,
R = {“geeks_are_geeks”, “geeks_dont_lose”, “geeks_for_geeks_is_love”}
Salida:
geeks para geeks es amor
geeks son geeks
geeks dont pierde

Entrada: S = «cool_wifi_ice»,
R = {«water_is_cool», «cold_ice_drink», «cool_wifi_speed»}
Salida:
cool wifi speed
water is cool
cold ice drink

Enfoque ingenuo: inserte todas las buenas palabras en un conjunto_desordenado y luego repita cada palabra de cada oración de la array de reseñas y mantenga un recuento de las buenas palabras comprobando si esta palabra está presente en ese conjunto de buenas palabras. Luego usamos un algoritmo de clasificación estable y clasificamos la array R de acuerdo con el recuento de buenas palabras en cada revisión presente en R. Está claro que la complejidad temporal de este método es mayor que O(N * NlogN) .

Enfoque eficiente: Haga un Trie de todas las buenas palabras y verifique la bondad de cada palabra en una revisión usando el trie.

  1. Inserta todas las buenas palabras en un trie.
  2. Para cada revisión, calcule el número de buenas palabras en ella verificando si una palabra dada existe en el trie o no.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define MAX 26
  
// Comparator function for sorting
bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
  
    // Compare the number of good words
    if (a.F == b.F)
        return a.S < b.S;
    return a.F > b.F;
}
  
// Structure of s Trie node
struct node {
    bool exist;
    node* arr[MAX];
    node(bool bul = false)
    {
        exist = bul;
        for (int i = 0; i < MAX; i++)
            arr[i] = NULL;
    }
};
  
// Function to add a string to the trie
void add(string s, node* trie)
{
    // Add a node to the trie
    int n = s.size();
    for (int i = 0; i < n; i++) {
  
        // If trie doesn't already contain
        // the current node then create one
        if (trie->arr[s[i] - 'a'] == NULL)
            trie->arr[s[i] - 'a'] = new node();
  
        trie = trie->arr[s[i] - 'a'];
    }
    trie->exist = true;
    return;
}
  
// Function that returns true if
// the trie contains the string s
bool search(string s, node* trie)
{
    // Search for a node in the trie
    for (int i = 0; i < s.size(); i++) {
        if (trie->arr[s[i] - 'a'] == NULL)
            return false;
  
        trie = trie->arr[s[i] - 'a'];
    }
    return trie->exist;
}
  
// Function to replace every '_' with a
// white space in the given string
void convert(string& str)
{
    // Convert '_' to spaces
    for (int i = 0; i < str.size(); i++)
        if (str[i] == '_')
            str[i] = ' ';
    return;
}
  
// Function to sort the array based on good words
void sortArr(string good, vector<string>& review)
{
  
    // Extract all the good words which
    // are '_' separated
    convert(good);
    node* trie = new node();
    string word;
    stringstream ss;
    ss << good;
  
    // Building the entire trie by stringstreaming
    // the 'good words' string
    while (ss >> word)
        add(word, trie);
    int k, n = review.size();
  
    // To store the number of good words
    // and the string index pairs
    vector<pair<int, int> > rating(n);
    for (int i = 0; i < n; i++) {
        convert(review[i]);
        ss.clear();
        ss << review[i];
        k = 0;
        while (ss >> word) {
  
            // If this word is present in the trie
            // then increment its count
            if (search(word, trie))
                k++;
        }
  
        // Store the number of good words in the
        // current string paired with its
        // index in the original array
        rating[i].F = k;
        rating[i].S = i;
    }
  
    // Using comparator function to
    // sort the array as required
    sort(rating.begin(), rating.end(), cmp);
  
    // Print the sorted array
    for (int i = 0; i < n; i++)
        cout << review[rating[i].S] << "\n";
}
  
// Driver code
int main()
{
  
    // String containing good words
    string S = "geeks_for_geeks_is_great";
  
    // Vector of strings to be sorted
    vector<string> R = { "geeks_are_geeks", "geeks_dont_lose",
                         "geeks_for_geeks_is_love" };
  
    // Sort the array based on the given conditions
    sortArr(S, R);
}
Producción:

geeks for geeks is love
geeks are geeks
geeks dont lose

Publicación traducida automáticamente

Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *