916. Word Subsets

Description

You are given two string arrays words1 and words2.

A string b is a subset of string a if every letter in b occurs in a including multiplicity.

• For example, "wrr" is a subset of "warrior" but is not a subset of "world".

A string a from words1 is universal if for every string b in words2, b is a subset of a.

Return an array of all the universal strings in words1. You may return the answer in any order.

 

Example 1:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
Output: ["apple","google","leetcode"]

 

Constraints:

• 1 <= words1.length, words2.length <= 104
• 1 <= words1[i].length, words2[i].length <= 10
• words1[i] and words2[i] consist only of lowercase English letters.
• All the strings of words1 are unique.

 

Solutions

Solution: Hash Map

• Time complexity: O(m⋅l1)+O(n⋅l2)
  • m: words1.length
  • n: words2.length
  • l1: words1[i] max length
  • l2: words2[i] max length
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string[]} words1
 * @param {string[]} words2
 * @return {string[]}
 */
const wordSubsets = function (words1, words2) {
  const BASE_CODE = 'a'.charCodeAt(0);
  const subset = Array.from({ length: 26 }, () => 0);

  const calculateSubset = word => {
    const result = Array.from({ length: 26 }, () => 0);

    for (const letter of word) {
      const code = letter.charCodeAt(0) - BASE_CODE;

      result[code] += 1;
    }
    return result;
  };

  for (const word of words2) {
    const currentSubset = calculateSubset(word);

    for (let code = 0; code < 26; code++) {
      subset[code] = Math.max(currentSubset[code], subset[code]);
    }
  }

  const result = [];

  const isUniversal = currentSubset => {
    for (let code = 0; code < 26; code++) {
      if (currentSubset[code] < subset[code]) return false;
    }
    return true;
  };

  for (const word of words1) {
    const currentSubset = calculateSubset(word);

    if (isUniversal(currentSubset)) {
      result.push(word);
    }
  }
  return result;
};