Show problems as
Classic problem #916MediumArrayHash TableString

Word Subsets

Real-world version: Labels That Cover Every Pattern
Tracked in this browser only
Read Word Subsets on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two lists of lowercase strings are given, labels and patterns, and no two labels are alike.

A label covers a pattern when, for every letter, the label holds that letter at least as many times as the pattern does.

Return the labels that cover every pattern in the list, in the order they appear in labels.

Examples

Example 1

Input
labels = ["carrot", "cabbage", "radish"], patterns = ["ca", "ar"]
Output
["carrot"]

Between them the patterns demand at least one `a`, one `c` and one `r`. Only the first label holds all three: the second has no `r` and the third no `c`.

Example 2

Input
labels = ["tin", "tint"], patterns = ["tt"]
Output
["tint"]

The pattern demands two `t`s, so holding a `t` is not enough. The first label has one and falls short; the second has two.

Example 3

Input
labels = ["a"], patterns = ["b"]
Output
[]

The only label has no `b` at all, so nothing covers the pattern.

Constraints

  • 1 <= labels.length <= 10^4
  • 1 <= patterns.length <= 10^4
  • 1 <= labels[i].length <= 10
  • 1 <= patterns[i].length <= 10
  • Every string is made of lowercase English letters.
  • No two labels are alike.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def word_subsets(labels: list[str], patterns: list[str]) -> list[str]:
Java
public List<String> wordSubsets(String[] labels, String[] patterns)

More on the same topics