0691. Stickers to Spell Word¶
题目信息¶
- 题号:
0691
- 难度:
Hard
- 主题:
字母多重集、贴纸重复使用、目标拼写、最少数量
- 原题:
- 重点:
每张贴纸提供其中全部字母且可只使用一部分、贴纸种类可无限重复取用、字母可重新排列、无法拼出时返回 -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,无论重复多少次都无法拼出目标。