# LeetCode: 691. 贴纸拼词¶

## 1、题目描述¶

输入：

["with", "example", "science"], "thehat"

3



输入：

["notice", "possible"], "basicbasic"

-1



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

## 2、解题思路¶

• 使用DFS加缓存
• 每一次构造新的字符串，进行递归

class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
from collections import Counter
from functools import lru_cache

count = [Counter(x) for x in stickers]

@lru_cache(None)
def dfs(s):
nonlocal count
if not s:
return 0

c = Counter(s)
ans = float('inf')

for t in count:
if s[-1] not in t:
continue
new_tar = ""

for k, v in c.items():
new_tar += k * (max(0, v - t[k]))
ans = min(ans, dfs(new_tar) + 1)
return ans

res = dfs(target)

return res if res != float('inf') else -1

• DFS加记忆化
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
from collections import Counter

count = [Counter(x) for x in stickers]
memo = {"": 0}

def dfs(s):
nonlocal count
if s in memo:
return memo[s]

c = Counter(s)
ans = float('inf')

for t in count:
if s[-1] not in t:
continue
new_tar = ""
for k, v in c.items():
new_tar += k * (max(0, v - t[k]))
if new_tar == "":
ans = 1
break
ans = min(ans, dfs(new_tar) + 1)
memo[s] = ans
return ans

res = dfs(target)

return res if res != float('inf') else -1