Show problems as
Classic problem #472HardArrayStringDynamic ProgrammingDepth-First SearchTrieSorting

Concatenated Words

Real-world version: Compound Labels In A Parts Catalogue
Tracked in this browser only
Read Concatenated Words on LeetCode(opens in a new tab)

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

A parts catalogue lists labels in labels. Every label is a non-empty string of lowercase letters and no label appears twice.

A label is compound when it can be cut into two or more pieces, laid end to end in order, where every piece is itself a label in the catalogue. The pieces may repeat, so a label may be built by using one catalogue label several times, and the piece order is simply left to right through the compound label. Because a compound label needs at least two pieces and no piece may be empty, every piece is strictly shorter than the compound label it builds.

A label that can only be produced as one whole piece, namely itself, is not compound.

Return every compound label in the catalogue, in any order.

Examples

Example 1

Input
labels = ["ab", "abc", "cd", "abcd"]
Output
["abcd"]

`"abcd"` cuts into `"ab"` and `"cd"`, two catalogue labels laid end to end. `"abc"` has cuts `"a"` plus `"bc"` and `"ab"` plus `"c"`, and neither pair is in the catalogue. `"ab"` and `"cd"` are two letters each and the catalogue has no single-letter label.

Example 2

Input
labels = ["a", "b", "ab", "ba", "aba", "bab"]
Output
["ab", "ba", "aba", "bab"]

`"ab"` is `"a"` then `"b"`, `"ba"` is `"b"` then `"a"`, `"aba"` is `"ab"` then `"a"`, and `"bab"` is `"ba"` then `"b"`. The single letters `"a"` and `"b"` cannot be cut into two non-empty pieces at all.

Example 3

Input
labels = ["solo"]
Output
[]

The catalogue has one label, and it can only be produced as itself in one piece, which the rules do not count.

Constraints

  • 1 <= labels.length <= 10^4
  • 1 <= labels[i].length <= 30
  • labels[i] consists of lowercase English letters only.
  • All the labels are different from one another.
  • The total length of all labels is at most 10^5.

The values you return may be in any order.

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 find_compound_labels(labels: list[str]) -> list[str]:
Java
public List<String> findCompoundLabels(String[] labels)

More on the same topics