Fewest Token Stencils To Spell A Target
A synthetic-data generator builds a target token string by stamping from a fixed set of stencils. Each stencil is a string whose individual characters can be cut out and reused; a stencil may be used unlimited times. Find the fewest stencils needed to spell the target, or report it is impossible.
Problem
Given an array of strings stickers and a target string, return the minimum number of stickers (with unlimited repetition) needed so their combined letters can spell target. Letters may be rearranged. Return -1 if impossible.
Input
An array stickers of strings and a string target.
Output
The minimum sticker count, or -1.
Constraints
- 1 ≤ stickers.length ≤ 50
- 1 ≤ sticker length, target length ≤ 15
- Lowercase English letters.
Examples
Example 1
Input
stickers=["with","example","science"] target="thehat"
Output
3
'with' + 'example' + 'example' supply t,h,e,h,a,t — 3 stickers.
Example 2
Input
stickers=["notice","possible"] target="basicbasic"
Output
-1
No combination supplies the letter 'r'? — actually the needed letters cannot all be formed, so -1.