题目描述

给你一个数组 favoriteCompanies，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。

请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。

样例

输入：
favoriteCompanies = [
    ["leetcode","google","facebook"],
    ["google","microsoft"],
    ["google","facebook"],
    ["google"],["amazon"]
]
输出：[0,1,4] 
解释：
favoriteCompanies[2]=["google","facebook"]
    是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集。

favoriteCompanies[3]=["google"] 
    是 favoriteCompanies[0]=["leetcode","google","facebook"] 
        和 favoriteCompanies[1]=["google","microsoft"] 的子集。
其余的收藏清单均不是其他任何人收藏的公司清单的子集。
因此，答案为 [0,1,4]。

输入：
favoriteCompanies = [
    ["leetcode","google","facebook"],
    ["leetcode","amazon"],
    ["facebook","google"]
]
输出：[0,1] 
解释：
favoriteCompanies[2]=["facebook","google"] 
    是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集。
因此，答案为 [0,1]。

输入：favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
输出：[0,1,2,3]

限制

• 1 <= favoriteCompanies.length <= 100
• 1 <= favoriteCompanies[i].length <= 500
• 1 <= favoriteCompanies[i][j].length <= 20
• favoriteCompanies[i] 中的所有字符串 各不相同。
• 用户收藏的公司清单也 各不相同，也就是说，即便我们按字母顺序排序每个清单，favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。
• 所有字符串仅包含小写英文字母。

算法

(哈希表，暴力枚举) $O(nL(S + L \log L + n)$

1. 将每个字符串映射到一个整数上，然后将每个人的整数列表从小到大排序。
2. 对于每个人 i，暴力枚举其他所有人 j，判断 f[i] 是否是 f[j] 的子集。

时间复杂度

• 对于每个人，映射的时间复杂度为 $O(LS)$，排序的时间复杂度为 $O(L \log L)$，其中 $L$ 为 favoriteCompanies[i].length 中的最大长度，$S$ 为字符串的最大长度。
• 判断子集的时间复杂度为 $O(L)$，暴力枚举 $O(n^2)$ 对。
• 故总时间复杂度为 $O(nL(S + \log L + n))$。

空间复杂度

• 需要额外 $O(nLS)$ 的空间存储哈希表和答案。

C++ 代码

class Solution {
public:
    bool isSubset(vector<int> &s1, vector<int> &s2) {
        int n = s1.size(), m = s2.size();
        if (n > m)
            return false;

        for (int i = 0, j = 0; j < m; j++)
            if (s1[i] == s2[j]) {
                i++;
                if (i == n)
                    return true;
            }

        return false;
    }

    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
        int n = favoriteCompanies.size();
        int m = 0;
        unordered_map<string, int> h;
        vector<vector<int>> f(n);

        for (int i = 0; i < n; i++) {
            for (const string &s : favoriteCompanies[i]) {
                if (h.find(s) == h.end())
                    h[s] = m++;
                f[i].push_back(h[s]);
            }
            sort(f[i].begin(), f[i].end());
        }

        vector<int> ans;
        for (int i = 0; i < n; i++) {
            bool flag = true;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (isSubset(f[i], f[j])) {
                    flag = false;
                    break;
                }
            }

            if (flag)
                ans.push_back(i);
        }

        return ans;
    }
};