All problems

Fewest Sign Tiles

Medium · trie

A sign shop makes banners by laying wooden tiles side by side in a row. Each tile has a short word of lowercase letters painted on it, and the letters on the row of tiles, read from left to right, form the banner text.

You are given the banner text to produce and a list tiles of the words the shop owns. The shop has as many copies of each tile as it needs, tiles cannot be cut or turned, and every tile in the row must be used whole.

Return the fewest tiles needed to spell banner exactly, or -1 if it cannot be spelled.

Examples

Example 1

Input: banner = "catsup", tiles = ["cat", "sup", "c", "a", "t", "s", "up"]

Output: 2

"cat" followed by "sup" uses two tiles. Any other split, such as "c", "a", "t", "s", "up", needs more.

Example 2

Input: banner = "abab", tiles = ["a", "ab"]

Output: 2

The tile "ab" can be used twice.

Example 3

Input: banner = "abc", tiles = ["ab", "bc"]

Output: -1

Tiles may not overlap, so "abc" cannot be spelled.

Constraints

• 1 <= len(banner) <= 2000
• 1 <= len(tiles) <= 2000
• 1 <= len(tiles[i]) <= 10
• Every string contains only lowercase letters.
• The words in tiles are all different.