Leecode #691 贴纸拼词

我们给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。

你希望从自己的贴纸集合中裁剪单个字母并重新排列它们，从而拼写出给定的目标字符串 target。

如果你愿意的话，你可以不止一次地使用每一张贴纸，而且每一张贴纸的数量都是无限的。

拼出目标 target 所需的最小贴纸数量是多少？如果任务不可能，则返回 -1。

示例

示例 1：

输入：

["with", "example", "science"], "thehat"
输出：

3
解释：

我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。

示例 2：

输入：

["notice", "possible"], "basicbasic"
输出：

-1
解释：

我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示：

• stickers 长度范围是 [1, 50]。
• stickers 由小写英文单词组成（不带撇号）。
• target 的长度在 [1, 15] 范围内，由小写字母组成。
• 在所有的测试案例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选取的，目标是两个随机单词的串联。
• 时间限制可能比平时更具挑战性。预计 50 个贴纸的测试案例平均可在35ms内解决。

解题思路

​ 主要有2中解题方法，一种是状态压缩dp，还有就是dfs。状态压缩加入了二进制的状态理解起来有点抽象，这里就讲一下比较容易理解的dfs吧，

​

dfs的思路很简单，关键在于优化和剪枝，每一步优化都大大缩短了运行时间

1. 判断无法拼成的情况
2. 只保留有用贴纸中有用的字符，然后根据贴纸字符数量和排序（逆序），这一步可以帮助dfs的时候快点到达最优的子情况
3. 数据清洗，若某个贴纸是另一个贴纸的子集合，则去掉
4. dfs，若深度已经超过当前最好的情况，且直接退出

代码如下：

class Solution:
    def minStickers(self, stickers, target: str) -> int:
        from collections import Counter

        all_words = set("".join(stickers))
        c = Counter(target)
       
        # 1. 判断无法拼成的情况
        if len(Counter(all_words)&c) != len(c):
            return -1

        # 2. 对贴纸进行排序
        data = [Counter(word)&c for word in stickers]
        data.sort(key=lambda x: sum(x.values()), reverse=True)


        # 3. 数据剪枝
        new_data = []
        for i in range(len(data)):
            flag = True
            for j in range(len(new_data)):
                if data[i]&new_data[j] == data[i]:
                    flag = False
                    break
            if flag :
                new_data.append(data[i])
        data = new_data


        # 4. dfs
        result = [len(target)]

        def dfs(i, n, c):
            # 如果已经比已有的结果大了，就不考虑这段分支
            if n >= result[0]:
                return
            # 保存这个分支的结果
            if sum(c.values()) == 0:
                result[0] = n
                return
            for j in range(i, len(data)):
                changed = {} # 保存更改的数据
                for w in data[j]:
                    if c[w] > 0:
                        changed[w] = c[w]
                        c[w] -= min(data[j][w], c[w])
                # 如果有合适的字符
                if len(changed) > 0:
                    dfs(j, n + 1, c)
                # 恢复
                for w in changed:
                    c[w] = changed[w]
        dfs(0, 0, c)
        return result[0]