809. Stickers to Spell Word (Recursive + Memo)

Given an array of sticker strings and a target string, return the minimum number of stickers needed so that their combined letters cover all letters of target. Each sticker can be used unlimited times. Return -1 if impossible. Input: JSON {stickers, target}.

Input: JSON {stickers, target}.

Output: Integer or -1.

Examples

Input: {"stickers":["with","example","science"],"target":"thehat"}
Output: 3
Explanation: Use 'with' (for t,h), 'example' (for e,a), 'with' again (for t,h) — or other combos totaling 3.

Input: {"stickers":["a","b","c"],"target":"abc"}
Output: 3
Explanation: One of each.

Constraints

• 1 <= stickers.length <= 10
• 1 <= stickers[i].length <= 10
• 1 <= target.length <= 10
• All lowercase

Asked by