题目描述

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 <= 100
• 1 <= favoriteCompanies[i].length <= 500
• 1 <= 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

C++ 代码

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;
    }
};