691. 贴纸拼词

大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

给出了 种不同的贴纸 stickers，需要用这些贴纸（每种贴纸的数目都是无限的），裁剪拼接出目标字符串 target。

求最少需要多少个贴纸。

画个图，解释一下示例一：

stickers = ["with","example","science"], 
target = "thehat"

解题方法

本题解是对本题的官方题解，进行更详细的讲解。

我们使用一个数字 标识 的每一个字符是否没被覆盖。
解释：

• 的二进制表示中，每一位对应了 中的每一个字符没被覆盖。（）。
• 因为 的长度在 1 和 15 之间，因此 可以用 类型 （共 32 位）。
• 注意 中每一位的顺序和 的顺序其实是反着的（的最低位对应了的最高位）

复杂度

• 时间复杂度：$O(N)$，是字符串长度。
• 空间复杂度：$O(1)$，没用额外空间。

  总结

1. 今天这个题主要是分情况讨论，想明白各种情况，思路清晰了的话，代码不难。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。