1.题目基本信息

1.1.题目描述

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。

注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。

1.2.题目地址

https://leetcode.cn/problems/stickers-to-spell-word/description/

2.解题方法

2.1.解题思路

记忆化搜索+状态压缩

2.2.解题步骤

第一步，搜索函数定义。mask为target没有匹配的部分的二进制状态；dfs(mask)表示在mask状态下，将target剩余需要匹配的字符匹配完，需要的最少贴纸数

第二步，递归出口。如果mask==0，表示target全部匹配完，不需要下一步匹配，即dfs(0)=0

第三步，状态转移。dfs(mask)=min([dfs(left)+1 for sticker in stickers])（left为让当前枚举的sticker中尽量多的字符匹配mask状态下的target中的字符后mask的状态）

第四步，dfs(1<<(len(target))-1)即为题解

3.解题代码

python3代码

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        # 思路：记忆化搜索+状态压缩
        n = len(target)
        # 第一步，搜索函数定义。mask为target没有匹配的部分的二进制状态；dfs(mask)表示在mask状态下，将target剩余需要匹配的字符匹配完，需要的最少贴纸数
        @cache
        def dfs(mask:int) -> int:
            # 第二步，递归出口。如果mask==0，表示target全部匹配完，不需要下一步匹配，即dfs(0)=0
            if mask == 0:
                return 0
            # 第三步，状态转移。dfs(mask)=min([dfs(left)+1 for sticker in stickers])（left为让当前枚举的sticker中尽量多的字符匹配mask状态下的target中的字符后mask的状态）
            ans = n + 1 # 哨兵
            for sticker in stickers:
                cnts = Counter(sticker)
                left = mask
                for i, ch in enumerate(target):
                    if mask & (1 << i) and cnts[ch] > 0:
                        cnts[ch] -= 1
                        left ^= (1 << i)
                if left != mask:
                    ans = min(ans, dfs(left) + 1)
            return ans
        # 第四步，dfs(1<<(len(target))-1)即为题解
        result = dfs((1 << n) - 1)
        return result if result <= n else -1

4.执行结果