1452.People Whose List of Favorite Companies Is Not a Subset of Another List¶
Tags: Medium String Sort Set
Given the array favoriteCompanies where favoriteCompanies[i] is the list of favorites companies for the ith person (indexed from 0).
Return the indices of people whose list of favorite companies is not a **subset* of any other list of favorites companies*. You must return the indices in increasing order.
Example 1:
Input: favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
Output: [0,1,4]
Explanation:
Person with index=2 has favoriteCompanies[2]=["google","facebook"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] corresponding to the person with index 0.
Person with index=3 has favoriteCompanies[3]=["google"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] and favoriteCompanies[1]=["google","microsoft"].
Other lists of favorite companies are not a subset of another list, therefore, the answer is [0,1,4].
Example 2:
Input: favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]
Output: [0,1]
Explanation: In this case favoriteCompanies[2]=["facebook","google"] is a subset of favoriteCompanies[0]=["leetcode","google","facebook"], therefore, the answer is [0,1].
Example 3:
Input: favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
Output: [0,1,2,3]
Constraints:
1 <= favoriteCompanies.length <= 1001 <= favoriteCompanies[i].length <= 5001 <= favoriteCompanies[i][j].length <= 20- All strings in
favoriteCompanies[i]are distinct. - All lists of favorite companies are distinct, that is, If we sort alphabetically each list then
favoriteCompanies[i] != favoriteCompanies[j]. - All strings consist of lowercase English letters only.
如果把每一个字符串的组合看成一个集合，那么这道题就是判断一个集合是否是其他集合的子集。如果一个集合是别的集合的子集，那么它的集合大小一定不能超过其他集合的最大长度，所以我们可以按照集合的长度进行排序，然后从头开始检验。
检验的过程中，使用set加快检验一个元素是否在另一个集合中存在。如果一个元素在某一个集合中不存在，那么就无需在检验当前集合，转而检验是否是下一个集合的子集。
类似的题目：1408.String Matching in an Array
class Solution {
struct Node
{
int originNum, len;
unordered_set<string> us;
bool operator<(const Node & obj) const
{
return len < obj.len;
}
};
public:
vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = favoriteCompanies.size();
vector<Node> seq(n);
for (int i = 0; i < n; ++i) {
seq[i].originNum = i;
seq[i].len = favoriteCompanies[i].size();
for (int j = 0; j < seq[i].len; ++j) {
seq[i].us.emplace(favoriteCompanies[i][j]);
}
}
sort(seq.begin(), seq.end());
vector<int> res;
for (int i = 0; i < n; ++i) {
auto & tmp = seq[i].us;
bool isSub = false;
for (int j = i + 1; j < n; ++j) {
bool allCanFind = true;
for (auto &e : tmp) {
if (seq[j].us.find(e) == seq[j].us.end()) { allCanFind = false; break; }
}
if (allCanFind) { isSub = true; break; }
}
if (!isSub) res.push_back(seq[i].originNum);
}
sort(res.begin(), res.end());
return res;
}
};