FunctionRacerProblemsRace

Spell It With Tiles

HardRecursionPython, JavaScript, TypeScript, Java, C++

Each string in tiles is printed on one tile, and several tiles may carry the same word. Lay some of the tiles in a row, each tile at most once, so that their words written one after another spell text exactly. Not every tile has to be used. Write each way down as a sentence: the words of the laid tiles in order, separated by single spaces.

Return every different sentence in sorted order, using plain string order, in which a space comes before every letter (so "a b" comes before "ab"). Tiles that carry the same word are interchangeable, so each sentence is listed once even when it can be laid with different tiles. If text cannot be spelled, return an empty list.

Backtracking is the natural approach: at each position of text, try each word that still has an unused tile and matches there, take one such tile, spell the rest, then put the tile back. A loop with an explicit stack of partial sentences works too.

Example 1

text "catsdog"
tiles ["cat","cats","dog","s","sdog"]
returns ["cat s dog","cat sdog","cats dog"]

cat can be followed by s and dog or by sdog, and cats can be followed by dog.

Example 2

text "banana"
tiles ["ba","na","nana"]
returns ["ba nana"]

ba na na would need two na tiles, but there is only one, so ba nana is the only sentence.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Recursion problems