Dadas N listas de strings, la tarea es encontrar el recuento de listas que no son una sublista de ninguna otra lista dada.
Ejemplos:
Entrada: [[“hola”, “hola”, “hola”], [“hola”, “adiós”], [“hola”, “hola”]]
Salida: 2
Explicación
La tercera lista es un subconjunto de la primera lista, por lo tanto, la primera y la segunda lista son las listas requeridas.
Entrada: [[“geeksforgeeks”, “geeks”], [“geeks”, “geeksforgeeks”]]
Salida: 0
Explicación: Ambas listas forman parte del mismo conjunto de strings.
Enfoque
Siga los pasos a continuación para resolver el problema:
- En primer lugar, enumere todas las strings posibles en todos los vectores, es decir, asígneles un número entero.
- Luego, use un Bitset para todas las listas individuales para almacenar las strings presentes en ellas.
- Compara los conjuntos de bits. Si uno de los conjuntos de bits es un subconjunto de otro, ignore esa lista. De lo contrario, inserte el índice de esa lista en un conjunto.
- Imprime todos los índices del conjunto.
El siguiente código es la implementación del enfoque anterior:
C++
// C++ program to find all lists
// which are not a subset of any
// other given lists
#include <bits/stdc++.h>
using namespace std;
#define N 50005
// Function to print all lists which
// are not a subset of any other lists
void findNonSubsets(vector<vector<string> >& v,
vector<int>& ans)
{
unordered_map<string, int> mp;
int id = 1;
// Enumerate all strings
// present in all lists
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < v[i].size(); j++) {
if (mp.count(v[i][j]) > 0)
continue;
mp[v[i][j]] = id++;
}
}
// Compute and store bitsets
// of all strings in lists
vector<bitset<N> > v1;
for (int i = 0; i < v.size(); i++) {
bitset<N> b;
for (int j = 0; j < v[i].size(); j++) {
b[mp[v[i][j]]] = 1;
}
v1.push_back(b);
}
for (int i = 0; i < v.size(); i++) {
bool flag = false;
for (int j = 0; !flag and j < v.size(); j++) {
if (i != j) {
// If one of the bitsets is
// a subset of another, the
// logical AND is equal to the
// subset(intersection operation)
if ((v1[i] & v1[j]) == v1[i]) {
flag = true;
}
}
}
if (!flag) {
ans.push_back(i);
}
}
return;
}
// Driver Program
signed main()
{
vector<vector<string> > v
= { { "hey", "hello", "hi" },
{ "hey", "bye" },
{ "hey", "hi" } };
vector<int> ans;
findNonSubsets(v, ans);
if (ans.size() == 0) {
cout << -1 << endl;
return 0;
}
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}
0 1
Complejidad Temporal: O ( N * M )
Espacio Auxiliar: O ( N * M )
Publicación traducida automáticamente
Artículo escrito por Shrey Tanna y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA