Spell It With Tiles
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
cat can be followed by s and dog or by sdog, and cats can be followed by dog.
Example 2
ba na na would need two na tiles, but there is only one, so ba nana is the only sentence.
Constraints
1 <= len(text) <= 201 <= len(tiles) <= 12and1 <= len(tiles[i]) <= 8textand every tile hold lowercase letters only- the answer holds at most 60 sentences
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Recursion problems
- Swap the Balanced PiecesHard
- Times Before PlusHard
- Valleys in the Folded StripHard
- Count the BoxesBeginner
- Digit TallyBeginner
- Equal NeighboursBeginner
- Halving TotalBeginner
- Largest DigitBeginner