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