{"id":4094,"date":"2018-09-30T07:39:24","date_gmt":"2018-09-30T14:39:24","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4094"},"modified":"2018-09-30T07:39:33","modified_gmt":"2018-09-30T14:39:33","slug":"leetcode-916-word-subsets","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-916-word-subsets\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 916. Word Subsets"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

We are given two arrays\u00a0A<\/code>\u00a0and\u00a0B<\/code>\u00a0of words.\u00a0 Each word is a string of lowercase letters.<\/p>\n

Now, say that\u00a0word\u00a0b<\/code>\u00a0is a subset of word\u00a0a<\/code>\u00a0<\/strong>if every letter in\u00a0b<\/code>\u00a0occurs in\u00a0a<\/code>,\u00a0including multiplicity<\/strong>.\u00a0 For example,\u00a0\"wrr\"<\/code>\u00a0is a subset of\u00a0\"warrior\"<\/code>, but is not a subset of\u00a0\"world\"<\/code>.<\/p>\n

Now say a word\u00a0a<\/code>\u00a0from\u00a0A<\/code>\u00a0is\u00a0universal<\/em>\u00a0if for every\u00a0b<\/code>\u00a0in\u00a0B<\/code>,\u00a0b<\/code>\u00a0is a subset of\u00a0a<\/code>.<\/p>\n

Return a list of all universal words in\u00a0A<\/code>.\u00a0 You can return the words in any order.<\/p>\n

Example 1:<\/strong><\/p>\n

Input: <\/strong>A = [\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"]<\/span>, B = [\"e\",\"o\"]<\/span>\r\nOutput: <\/strong>[\"facebook\",\"google\",\"leetcode\"]<\/span>\r\n<\/pre>\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>A = [\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"]<\/span>, B = [\"l\",\"e\"]<\/span>\r\nOutput: <\/strong>[\"apple\",\"google\",\"leetcode\"]<\/span>\r\n<\/pre>\n
Example 3:<\/strong><\/p>\n
Input: <\/strong>A = [\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"]<\/span>, B = [\"e\",\"oo\"]<\/span>\r\nOutput: <\/strong>[\"facebook\",\"google\"]<\/span>\r\n<\/pre>\n
Example 4:<\/strong><\/p>\n
Input: <\/strong>A = [\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"]<\/span>, B = [\"lo\",\"eo\"]<\/span>\r\nOutput: <\/strong>[\"google\",\"leetcode\"]<\/span>\r\n<\/pre>\n
Example 5:<\/strong><\/p>\n
Input: <\/strong>A = [\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"]<\/span>, B = [\"ec\",\"oc\",\"ceo\"]<\/span>\r\nOutput: <\/strong>[\"facebook\",\"leetcode\"]<\/span>\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. 1 <= A.length, B.length <= 10000<\/code><\/li>\n
  2. 1 <= A[i].length, B[i].length\u00a0<= 10<\/code><\/li>\n
  3. A[i]<\/code>\u00a0and\u00a0B[i]<\/code>\u00a0consist only of lowercase letters.<\/li>\n
  4. All words in\u00a0A[i]<\/code>\u00a0are unique: there isn’t\u00a0i != j<\/code>\u00a0with\u00a0A[i] == A[j]<\/code>.<\/li>\n<\/ol>\n
    Solution: Hashtable<\/h1>\n
    Find the max requirement for each letter from B.<\/p>\n
    Time complexity: O(|A|+|B|)<\/p>\n
    Space complexity: O(26)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua, 104 ms\r\nclass Solution {\r\npublic:\r\n  vector<string> wordSubsets(vector<string>& A, vector<string>& B) {\r\n    vector<int> req(26);\r\n    for (const string& b : B) {\r\n      vector<int> cur(getCount(b));\r\n      for (int i = 0; i < 26; ++i)\r\n        req[i] = max(req[i], cur[i]);\r\n    }\r\n    \r\n    vector<string> ans;    \r\n    for (const string& a : A) {\r\n      vector<int> cur(getCount(a));\r\n      bool universal = true;\r\n      for (int i = 0; i < 26; ++i)\r\n        if (cur[i] < req[i]) {\r\n          universal = false;\r\n          break; \r\n        }\r\n      if (universal) ans.push_back(a);\r\n    }\r\n    return ans;\r\n  }\r\nprivate:\r\n  vector<int> getCount(const string& a) {\r\n    vector<int> count(26);\r\n    for (char c : a)\r\n      ++count[c - 'a'];\r\n    return count;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem We are given two arrays\u00a0A\u00a0and\u00a0B\u00a0of words.\u00a0 Each word is a string of lowercase letters. Now, say that\u00a0word\u00a0b\u00a0is a subset of word\u00a0a\u00a0if every letter in\u00a0b\u00a0occurs…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70,47],"tags":[82,177,419],"class_list":["post-4094","post","type-post","status-publish","format-standard","hentry","category-hashtable","category-string","tag-hashtable","tag-medium","tag-union","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4094","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=4094"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4094\/revisions"}],"predecessor-version":[{"id":4096,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4094\/revisions\/4096"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4094"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4094"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4094"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}