Description#
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.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
d = {}
idx = 0
t = []
for v in favoriteCompanies:
for c in v:
if c not in d:
d[c] = idx
idx += 1
t.append({d[c] for c in v})
ans = []
for i, nums1 in enumerate(t):
ok = True
for j, nums2 in enumerate(t):
if i == j:
continue
if not (nums1 - nums2):
ok = False
break
if ok:
ans.append(i)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
Map<String, Integer> d = new HashMap<>();
int idx = 0;
int n = favoriteCompanies.size();
Set<Integer>[] t = new Set[n];
for (int i = 0; i < n; ++i) {
var v = favoriteCompanies.get(i);
for (var c : v) {
if (!d.containsKey(c)) {
d.put(c, idx++);
}
}
Set<Integer> s = new HashSet<>();
for (var c : v) {
s.add(d.get(c));
}
t[i] = s;
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; ++i) {
boolean ok = true;
for (int j = 0; j < n; ++j) {
if (i != j) {
if (t[j].containsAll(t[i])) {
ok = false;
break;
}
}
}
if (ok) {
ans.add(i);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public:
vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
unordered_map<string, int> d;
int idx = 0, n = favoriteCompanies.size();
vector<unordered_set<int>> t(n);
for (int i = 0; i < n; ++i) {
auto v = favoriteCompanies[i];
for (auto& c : v) {
if (!d.count(c)) {
d[c] = idx++;
}
}
unordered_set<int> s;
for (auto& c : v) {
s.insert(d[c]);
}
t[i] = s;
}
vector<int> ans;
for (int i = 0; i < n; ++i) {
bool ok = true;
for (int j = 0; j < n; ++j) {
if (i == j) continue;
if (check(t[i], t[j])) {
ok = false;
break;
}
}
if (ok) {
ans.push_back(i);
}
}
return ans;
}
bool check(unordered_set<int>& nums1, unordered_set<int>& nums2) {
for (int v : nums1) {
if (!nums2.count(v)) {
return false;
}
}
return true;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| func peopleIndexes(favoriteCompanies [][]string) []int {
d := map[string]int{}
idx, n := 0, len(favoriteCompanies)
t := make([]map[int]bool, n)
for i, v := range favoriteCompanies {
for _, c := range v {
if _, ok := d[c]; !ok {
d[c] = idx
idx++
}
}
s := map[int]bool{}
for _, c := range v {
s[d[c]] = true
}
t[i] = s
}
ans := []int{}
check := func(nums1, nums2 map[int]bool) bool {
for v, _ := range nums1 {
if _, ok := nums2[v]; !ok {
return false
}
}
return true
}
for i := 0; i < n; i++ {
ok := true
for j := 0; j < n; j++ {
if i == j {
continue
}
if check(t[i], t[j]) {
ok = false
break
}
}
if ok {
ans = append(ans, i)
}
}
return ans
}
|
