{"id":6767,"date":"2020-05-16T21:44:35","date_gmt":"2020-05-17T04:44:35","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6767"},"modified":"2020-05-16T21:44:52","modified_gmt":"2020-05-17T04:44:52","slug":"leetcode-1452-people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1452-people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1452. People Whose List of Favorite Companies Is Not a Subset of Another List"},"content":{"rendered":"\n<p>Given the array&nbsp;<code>favoriteCompanies<\/code>&nbsp;where&nbsp;<code>favoriteCompanies[i]<\/code>&nbsp;is the list of favorites companies for the&nbsp;<code>ith<\/code>&nbsp;person (<strong>indexed from 0<\/strong>).<\/p>\n\n\n\n<p><em>Return the indices of people whose list of favorite companies is not a&nbsp;<strong>subset<\/strong>&nbsp;of any other list of favorites companies<\/em>. You must return the indices&nbsp;in increasing order.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> favoriteCompanies = [[\"leetcode\",\"google\",\"facebook\"],[\"google\",\"microsoft\"],[\"google\",\"facebook\"],[\"google\"],[\"amazon\"]]\n<strong>Output:<\/strong> [0,1,4] \n<strong>Explanation:<\/strong> \nPerson 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. \nPerson with index=3 has favoriteCompanies[3]=[\"google\"] which is a subset of favoriteCompanies[0]=[\"leetcode\",\"google\",\"facebook\"] and favoriteCompanies[1]=[\"google\",\"microsoft\"]. \nOther lists of favorite companies are not a subset of another list, therefore, the answer is [0,1,4].\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> favoriteCompanies = [[\"leetcode\",\"google\",\"facebook\"],[\"leetcode\",\"amazon\"],[\"facebook\",\"google\"]]\n<strong>Output:<\/strong> [0,1] \n<strong>Explanation:<\/strong> In this case favoriteCompanies[2]=[\"facebook\",\"google\"] is a subset of favoriteCompanies[0]=[\"leetcode\",\"google\",\"facebook\"], therefore, the answer is [0,1].\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> favoriteCompanies = [[\"leetcode\"],[\"google\"],[\"facebook\"],[\"amazon\"]]\n<strong>Output:<\/strong> [0,1,2,3]\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;=&nbsp;favoriteCompanies.length &lt;= 100<\/code><\/li><li><code>1 &lt;=&nbsp;favoriteCompanies[i].length &lt;= 500<\/code><\/li><li><code>1 &lt;=&nbsp;favoriteCompanies[i][j].length &lt;= 20<\/code><\/li><li>All strings in&nbsp;<code>favoriteCompanies[i]<\/code>&nbsp;are&nbsp;<strong>distinct<\/strong>.<\/li><li>All lists of favorite companies are&nbsp;<strong>distinct<\/strong>, that is, If we sort alphabetically each list then&nbsp;<code>favoriteCompanies[i] != favoriteCompanies[j].<\/code><\/li><li>All strings consist of lowercase English letters only.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Hashtable<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n*n*m)<br>Space complexity: O(n*m)<br>where n is the # of people, m is the # of companies<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 664 ms 58.4 MB\nclass Solution {\npublic:\n  vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {\n    const int n = favoriteCompanies.size();\n    vector<unordered_set<string>> m;\n    for (const auto& c : favoriteCompanies)\n      m.emplace_back(begin(c), end(c));\n    vector<int> ans;\n    for (int i = 0; i < n; ++i) {\n      bool valid = true;\n      for (int j = 0; j < n &#038;&#038; valid; ++j) {\n        if (i == j) continue;\n        bool subset = true;\n        for (const auto&#038; s : m[i])\n          if (!m[j].count(s)) {\n            subset = false;\n            break;\n          }\n        if (subset) {\n          valid = false;\n          break;\n        }\n      }\n      if (valid)\n        ans.push_back(i);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>Use int as key to make it faster.<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 476 ms, 48.7 MB\nclass Solution {\npublic:\n  vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {\n    const int n = favoriteCompanies.size();\n    unordered_map<string, int> ids;\n    vector<unordered_set<int>> m;\n    for (const auto& companies : favoriteCompanies) {\n      m.push_back({});\n      for (const auto& c : companies) {\n        if (!ids.count(c))\n          ids[c] = ids.size();\n        m.back().insert(ids[c]);\n      }\n    }\n    vector<int> ans;\n    for (int i = 0; i < n; ++i) {\n      bool valid = true;\n      for (int j = 0; j < n &#038;&#038; valid; ++j) {\n        if (i == j) continue;\n        bool subset = true;\n        for (const auto&#038; s : m[i])\n          if (!m[j].count(s)) {\n            subset = false;\n            break;\n          }\n        if (subset) {\n          valid = false;\n          break;\n        }\n      }\n      if (valid) ans.push_back(i);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given the array&nbsp;favoriteCompanies&nbsp;where&nbsp;favoriteCompanies[i]&nbsp;is the list of favorites companies for the&nbsp;ith&nbsp;person (indexed from 0). Return the indices of people whose list of favorite companies is not&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,493],"class_list":["post-6767","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-subset","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6767","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6767"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6767\/revisions"}],"predecessor-version":[{"id":6769,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6767\/revisions\/6769"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6767"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6767"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6767"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}