贴纸拼词

难度: Hard

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

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

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

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

示例 1：

输入： stickers = ["with","example","science"], target = "thehat"
输出：3
解释：
我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。

示例 2:

输入：stickers = ["notice","possible"], target = "basicbasic"
输出：-1
解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示:

n == stickers.length
1 <= n <= 50
1 <= stickers[i].length <= 10
1 <= target.length <= 15
stickers[i] 和 target 由小写英文单词组成

Submission

运行时间: 112 ms

内存: 0.0 MB

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        stickers.sort(key=len)
        freq = [Counter(x) for x in stickers]
        memo = {}
        def dfs(word):
            if word in memo:
                return memo[word]
            res = float('inf')
            for w in freq:
                if word[0] not in w:
                    continue
                new = word
                for c in w:
                    new = new.replace(c, '', w[c])
                if new == '':
                    res = 1
                    break
                elif new != word:
                    res = min(res, 1 + dfs(new))
            memo[word] = res
            return res
        res = dfs(target)
        return res if res < float('inf') else -1

Explain

这个题解采用了记忆化搜索的方法。首先对贴纸数组按照长度排序，然后用 Counter 统计每个贴纸中字母的频次。在 dfs 函数中，如果当前单词已经被记忆，直接返回记忆的结果。否则，遍历每个贴纸，如果贴纸中包含目标单词的第一个字母，则将目标单词中贴纸所包含的字母全部删去，递归处理剩余的单词。如果剩余单词为空，说明找到了一种拼接方案；如果剩余单词不为空但与原单词不同，则更新最小贴纸数量。最后将目标单词和最小贴纸数记录在备忘录中并返回结果。

时间复杂度: O(n * m * 2^m)

空间复杂度: O(m * 2^m)

```python
class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        # 按照贴纸的长度排序
        stickers.sort(key=len)
        # 统计每个贴纸中字母的频次
        freq = [Counter(x) for x in stickers]
        # 备忘录，用于记录每个状态的最小贴纸数
        memo = {}
        
        def dfs(word):
            # 如果当前状态已经被记忆，直接返回结果
            if word in memo:
                return memo[word]
            
            res = float('inf')
            # 遍历每个贴纸
            for w in freq:
                # 如果贴纸中不包含目标单词的第一个字母，跳过
                if word[0] not in w:
                    continue
                
                new = word
                # 将目标单词中贴纸所包含的字母全部删去
                for c in w:
                    new = new.replace(c, '', w[c])
                
                # 如果剩余单词为空，说明找到了一种拼接方案，更新最小贴纸数
                if new == '':
                    res = 1
                    break
                # 如果剩余单词不为空但与原单词不同，递归处理剩余单词，更新最小贴纸数
                elif new != word:
                    res = min(res, 1 + dfs(new))
            
            # 将当前状态和最小贴纸数记录在备忘录中
            memo[word] = res
            return res
        
        res = dfs(target)
        # 如果最小贴纸数为正无穷，说明无法拼接出目标单词，返回-1；否则返回最小贴纸数
        return res if res < float('inf') else -1
```

Explore

记忆化搜索是一种有效的方法来优化递归算法，尤其是在解决组合问题时，它可以防止重复计算已经解决的子问题。在这个题解中，由于目标词可能会通过不同的贴纸组合以不同的方式被构建，使用记忆化搜索可以灵活地处理这种组合性质，同时通过备忘录存储已经计算过的结果来避免不必要的重复计算。动态规划通常适用于问题具有明确的递推关系和较小的状态空间，而本题的状态空间较大且不容易直接定义状态转移方程，因此采用记忆化搜索更为合适。

按长度排序贴纸数组可能在某些情况下提高效率，因为较长的贴纸可能包含更多的字符，从而在早期尝试时可能更快地减少目标单词的长度。这种策略可能帮助算法快速找到需要更少贴纸的解决方案，尤其是在目标单词较长且贴纸可提供大量字符时。然而，这种排序并不总是保证效率提升，因为实际效果还取决于贴纸中字符的种类和分布。

在这个题解中，`状态`指的是在递归过程中当前处理的目标单词的剩余部分。通过使用备忘录（memoization），每个特定的单词配置（即状态）只计算一次并存储其结果。当这个状态再次出现在递归调用中时，可以直接从备忘录中获取结果，而不需要重新计算。因此，每个状态最多被访问一次指的是每种单词配置在整个计算过程中至多被解决一次，避免了不必要的计算重复。

这种方法可能会忽略掉某些潜在的有效组合。因为一个有效的贴纸组合可能不需要从目标单词的第一个字母开始匹配。例如，如果目标单词的后半部分包含某个贴纸可以完全覆盖的字母，那么从这个贴纸开始可能是一个更优的选择。跳过不包含目标单词第一个字母的贴纸是一种启发式方法，它可以减少搜索空间和计算量，但可能牺牲了解的全面性。在实际应用中，这种方法需要根据具体问题和数据特性进行权衡。