প্রতিটি ব্যক্তির ফেভারিট কোম্পানির লিস্ট দেওয়া আছে। যেসব ব্যক্তির লিস্ট অন্য কারো লিস্টের সাবসেট নয়, তাদের ইনডেক্স বের করতে হবে।
ইনপুট: [["TCS","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]] → আউটপুট: [0,1,4]
সমাধানের ধাপগুলো:
প্রতিটি লিস্ট সর্ট করব
ok(a,b)ফাংশন:aকিbএর সাবসেট (টু-পয়েন্টার দিয়ে)প্রতি ব্যক্তি
iএর জন্য সবj != iচেক করব:ok(f[i], f[j])যদি কোনো
jএর জন্য সাবসেট হয়, তবে বাদ দিববাকি ইনডেক্স সেটে রাখব এবং রিটার্ন করব
উদাহরণ
নিচের কোডটি দেখুন −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for(int i = 0; i < v.size(); i++) {
cout << v[i] << ", ";
}
cout << "]" << endl;
}
class Solution {
public:
bool ok(vector<string>& a, vector<string>& b) {
int cnt = 0, i = 0, j = 0;
while (i < a.size() && j < b.size()) {
if (a[i] == b[j]) {
i++; j++; cnt++;
} else if (a[i] < b[j]) {
i++;
} else {
j++;
}
}
return cnt < a.size();
}
vector<int> peopleIndexes(vector<vector<string>>& f) {
set<int> s;
int n = f.size();
for (int i = 0; i < n; i++)
sort(f[i].begin(), f[i].end());
for (int i = 0; i < n; i++) {
bool c = true;
for (int j = 0; j < n; j++) {
if (i == j) continue;
c &= ok(f[i], f[j]);
}
if (c)
s.insert(i);
}
return vector<int>(s.begin(), s.end());
}
};
int main() {
Solution ob;
vector<vector<string>> v = {{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}};
print_vector(ob.peopleIndexes(v));
}
ইনপুট
{{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}}
আউটপুট
[0, 1, 4, ]
