Fewest Phrases
Medium · trie
A sign-maker has a box of ready-made tiles. Each tile carries one phrase from the list phrases, and there are as many copies of each tile as you like. Tiles are laid side by side in a row with nothing in between, so the phrases are simply joined one after another.
Return the smallest number of tiles whose phrases, joined in order, spell exactly message. If the message cannot be spelled that way, return -1.
Examples
Example 1
Input: message = "catsanddogs", phrases = ["cat", "cats", "and", "sand", "dog", "dogs"]
Output: 3
"cats" + "and" + "dogs" uses 3 tiles. "cat" + "sand" + "dogs" also uses 3, and nothing shorter works.
Example 2
Input: message = "aaaaa", phrases = ["aa", "aaa"]
Output: 2
"aa" + "aaa" spells five letters with 2 tiles.
Example 3
Input: message = "hello", phrases = ["he", "ll"]
Output: -1
"he" and "ll" cover the first four letters, but nothing supplies the final "o".
Constraints
- 1 <= len(message) <= 2000
- 1 <= len(phrases) <= 1000
- 1 <= len(phrases[i]) <= 20
- message and every phrase use only lowercase English letters
- All phrases are different from each other