1452-收藏清单

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

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

示例 1：

**输入：** 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] 。

示例 2：

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

示例 3：

**输入：** 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] 仍然成立。
• 所有字符串仅包含小写英文字母。

Problem: 1452. 收藏清单

[TOC]

思路

讲述看到这一题的思路

解题方法

描述你的解题方法

复杂度

• 时间复杂度:

  添加时间复杂度, 示例： O(n)

• 空间复杂度:

  添加空间复杂度, 示例： O(n)

Code

[]

class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
        int n = favoriteCompanies.size();
        vector<vector<int>>vIndex(n);
        unordered_map<string, int>mIndex;
        int j = 0;

        //将字符串映射为index降低匹配复杂度
        for(int i = 0; i < n; i++) {
            for(auto &c : favoriteCompanies[i]) {
                if(!mIndex.count(c)) mIndex[c] = j++;
                vIndex[i].push_back(mIndex[c]);
            }
            std::sort(vIndex[i].begin(), vIndex[i].end());
        }

        set<int> s;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(j != i && !s.count(j)) {
                    //c++ includes 函数，必须数组排序之后才能使用
                    if(includes(vIndex[i].begin(), vIndex[i].end(), vIndex[j].begin(), vIndex[j].end())) {
                        s.insert(j);
                    }
                }
            }
        }
        vector<int> ans;
        for(int i =0; i < n; i++) {
            if(!s.count(i))
                ans.push_back(i);
        } 
        return ans;

    }
};