0691. Stickers to Spell Word

题目信息

题号:

0691

难度:

Hard

主题:

字母多重集、贴纸重复使用、目标拼写、最少数量

原题:

LeetCode 0691

重点:

每张贴纸提供其中全部字母且可只使用一部分、贴纸种类可无限重复取用、字母可重新排列、无法拼出时返回 -1

题目重述

给定小写英文单词数组 stickers 和目标字符串 target。每取得一张贴纸,就获得该贴纸中每个字符的一份,可以剪下其中任意部分并重新排列,用来组成 target。

每种贴纸可以取得任意多张,未使用的贴纸字母可以丢弃;目标中的每个字符出现次数都必须被足够的贴纸字符覆盖。返回拼出 target 所需的最少贴纸数,若无法完成则返回 -1。stickers.length 位于 [1, 50],每个贴纸长度位于 [1, 10],target.length 位于 [1, 15]。

自建示例

需要重复使用同一种贴纸:

输入:stickers = ["ab","bc"],target = "aabbc"
输出:3
解释:使用两张 "ab" 提供两个 a 和两个 b,再使用一张 "bc" 提供 c;多出的 b 可以不用。

缺少目标所需字符:

输入:stickers = ["ab","cd"],target = "ace"
输出:-1
解释:所有贴纸都不含字符 e,无论重复多少次都无法拼出目标。