1345. Stickers to Spell Word — Bitmask DP

You have an unlimited supply of each sticker, and each sticker is a string whose letters you may cut out and use. Return the minimum number of stickers needed to spell out the target string, or -1 if it is impossible. Letters within a sticker can be used in any order and each sticker may be used many times.

Input: A JSON object {"stickers": [<strings>], "target": <string>}.

Output: Return the minimum sticker count, or -1 when the target cannot be spelled.

Examples

Input: {"stickers":["with","example","science"],"target":"thehat"}
Output: 3
Explanation: Three stickers are needed to spell the target.

Input: {"stickers":["notice","possible"],"target":"basicbasic"}
Output: -1
Explanation: Some needed letters never appear -> -1.

Constraints

• 1 <= len(stickers) <= 50
• 1 <= len(target) <= 15
• lowercase English letters

Asked by