Contagem de listas que não são um subconjunto de nenhuma outra lista fornecida
Dadas N listas de strings, a tarefa é encontrar a contagem de listas que não são sublistas de nenhuma outra lista fornecida.
Exemplos:
Entrada: [[“hey”, “hi”, “hello”], [“hey”, “bye”], [“hey”, “hi”]]
Saída: 2
Explicação
A terceira lista é um subconjunto da primeira lista, portanto, a primeira e a segunda lista são as listas necessárias.
Entrada: [[“geeksforgeeks”, “geeks”], [“geeks”, “geeksforgeeks”]]
Saída: 0
Explicação: Ambas as listas são compostas pelo mesmo conjunto de strings.
Abordagem
Siga as etapas abaixo para resolver o problema:
- Em primeiro lugar, enumere todas as strings possíveis em todos os vetores, ou seja, atribua-lhes um número inteiro.
- Em seguida, use um Bitset para todas as listas individuais para armazenar as strings presentes nelas.
- Compare os bitsets. Se um dos bitsets for um subconjunto de outro, ignore essa lista. Caso contrário, insira o índice dessa lista em um conjunto.
- Imprima todos os índices do conjunto.
O código abaixo é a implementação da abordagem acima:
// 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
Complexidade de tempo: O (N * M)
Espaço auxiliar: O (N * M)
Aprendendo inglês e usando o Anki? Use o Faluchu e esqueça os cartões. É gratis!
Usar o Faluchu