Word Subsets
Medium · strings
You are given two lists of lower-case words, words1 and words2.
Call a word a covering a word b if a has at least as many of each letter as b does. The order of the letters does not matter, only the counts: "garden" covers "nag" and "red", but it does not cover "gag" because it has only one g.
A word from words1 is universal if it covers every word in words2. Each word in words2 is checked on its own, so the letters are not added up across words: "ab" covers both "ab" and "ab".
Return every universal word from words1, in the order they appear in words1. A word that appears more than once in words1 is returned once for each appearance. If there are none, return an empty list.
Examples
Example 1
Input: words1 = ["garden", "orange", "danger", "ranged", "greed"], words2 = ["er", "ga"]
Output: ["garden", "orange", "danger", "ranged"]
"greed" has no a, so it does not cover "ga". The other four contain e, r, g and a.
Example 2
Input: words1 = ["balloon", "ballot", "bottle", "tollbooth"], words2 = ["ll", "oo"]
Output: ["balloon", "tollbooth"]
"ballot" has only one o and "bottle" has only one l.
Example 3
Input: words1 = ["ab", "abb", "ba"], words2 = ["ab", "ab"]
Output: ["ab", "abb", "ba"]
Each word in words2 is checked separately, so one a and one b are enough.
Constraints
- 1 <= len(words1), len(words2) <= 10^4
- 1 <= len(words1[i]), len(words2[i]) <= 10
- Every word contains only lower-case English letters.