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 pierdeEntrada: 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.
- Inserta todas las buenas palabras en un trie.
- 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);
}
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