Show problems as
Classic problem #140HardArrayHash TableStringDynamic ProgrammingBacktrackingTrieMemoization

Word Break II

Real-world version: Tape Track Splits
Tracked in this browser only
Read Word Break II on LeetCode(opens in a new tab)

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

An archive holds reel tapes whose printed labels ran the track names together with every separator worn away. You are given the label tape and titles, the catalogue of track names the archive recognises.

Restore the label. A restoration is an ordered run of catalogue titles whose letters, written one after another with nothing between them, give tape exactly. A title may be reused as often as it helps, and the catalogue may hold titles that no restoration uses.

Return every restoration as a string, with one blank space between neighbouring titles. The restorations may come back in any order. Return an empty list when the label cannot be restored from the catalogue at all.

Examples

Example 1

Input
tape = "dubdub", titles = ["dub", "du", "b", "bdub"]
Output
["du b du b", "du b dub", "du bdub", "dub du b", "dub dub"]

Three runs of titles spell the label: dub then dub, du then bdub, and du then b then du then b.

Example 2

Input
tape = "harpsong", titles = ["harp", "song", "harps", "on", "g"]
Output
["harp song", "harps on g"]

The label splits after harp and after harps, so two restorations exist and both are reported.

Example 3

Input
tape = "mix", titles = ["mi"]
Output
[]

No catalogue title covers the trailing x, so nothing can be restored and the list is empty.

Constraints

  • 1 <= tape.length <= 20
  • 1 <= titles.length <= 1000
  • 1 <= titles[i].length <= 10
  • tape and titles[i] hold lowercase English letters only
  • The titles are pairwise distinct
  • The input is chosen so the returned list holds at most 10^5 restorations

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 tape_track_splits(tape: str, titles: list[str]) -> list[str]:
Java
public List<String> tapeTrackSplits(String tape, List<String> titles)

More on the same topics