Question

1452. People Whose List of Favorite Companies Is Not a Subset of Another List

中文文档

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 <= 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.

Solutions

Solution 1

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

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

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

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
}