Leetcode Link: 691. 贴纸拼词 - 力扣（LeetCode）
题目
我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。
注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。
从暴力递归到动态规划记忆化搜索
好好解释解释本题
- 可以看出，贴纸算是我的字典，不过字典的每个元素是可以再分的，就是可以继续分解的。
- 每个贴纸是无限的，但是一张贴纸上的原子是有限的。
- 要的是最小的贴纸数量
暴力递归
可以发现，字符和贴纸的顺序都不是重要的，我只要贴纸提供的东西能够和字符里的东西一一对应就行 同时也注意到，字符也不一定要有固定的相对顺序，因为贴纸可以剪的很碎，如果剪成一个字母，实际上就不要求字符的顺序了。
这样的话，我们就可以先对字符排序了
就拿可以拿的贴纸解决第一个字母
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
res = self.process(stickers, target)
if res == float('inf'): # 表示都不行，就返回-1
return -1
else:
return res
# 给定当前剩余的字符和所有贴纸，返回最小贴纸数量
def process(self, stickers, cur):
# base case: 如果当前的字符一个东西也没有了，那就是需要0张
if cur=="":
return 0
# 给定结果一个初始状态，表示无法拼成（-1不行，会在min处出错）
res = float('inf')
# 轮流选择贴纸来作为第一张
# 如果选择完之后剩余的贴纸有变化，则送到同样的子问题中
# 反之说明该贴纸没用，就不用送到子问题了。
for s in stickers:
rest = self.minus(cur, s) # 从 cur 中扣掉 s 中的每一个字母
if len(rest) < len(cur):
res = min(res, self.process(stickers, rest))
if res == float('inf'):
return float('inf')
else:
return res + 1 # 加1表示加上本函数中选择的贴纸
def minus(self, target, strs):
for s in strs:
target = target.replace(s, "", 1)
return target记忆化搜索
画调用栈来思考能不能记忆化搜索
如果想用一个memo来记录以往的答案，需要意识到字符串内的字母顺序不同，会导致不同的key，所以需要先对其排序，保证key的唯一性后才能使用记忆化搜索。
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
self.memo = {}
# 对一个字符串排序（还是得到的字符串） ！ 注意这里不是列表！
target = sorted(target)
target = "".join(target)
res = self.process(stickers, target)
if res == float('inf'):
return -1
else:
return res
# 给定当前的字符和所有贴纸，返回最小贴纸数量
def process(self, stickers, cur):
# base case: 如果当前的字符一个东西也没有了，那就是需要0张
if cur=="":
return 0
if cur in self.memo:
return self.memo[cur]
# 给定结果一个初始状态，表示无法拼成（-1不行，会在min处出错）
res = float('inf')
# 轮流选择贴纸来作为第一张
# 如果选择完之后剩余的贴纸有变化，则送到同样的子问题中
# 反之说明该贴纸没用，就不用送到子问题了。
for s in stickers:
rest = self.minus(cur, s) # 从 cur 中扣掉 s 中的每一个字母
if len(rest) < len(cur):
rest = sorted(rest) # 必需排序
rest = "".join(rest)
res = min(res, self.process(stickers, rest))
if res == float('inf'):
self.memo[cur] = float('inf')
return float('inf')
else:
self.memo[cur] = res + 1
return res + 1
def minus(self, target, strs):
# 这里也可以用词频来做
# 两个dict，表示target和strs的词频（每个字母出现多少次）
for s in strs:
target = target.replace(s, "", 1)
return target至此，我们发现这个不能用dp，因为依赖的是字符串，字符串没法变成严格的表依赖
一种剪枝的方法
利用词频表进行剪枝 同时利用词频表速度也会快一点
任何一个顺序不重要的字符串，都可以用一个[1x26]的数字表示，每个位置表示对应字母的出现次数。
这样后面处理的速度可能会快一点
剪枝思路
我们前面的思路是轮流选择贴纸做第一张。然而，那些不能消去当前第一个字母的贴纸，但是能消去后面的字母的贴纸我们也选择了。这种枝干我们就可以剪去。 即，如果当前贴纸不包含第一个字母，则跳过。用词频表很好解决。
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
n = len(stickers)
dicts = [[0 for _ in range(26)] for _ in range(n)]
tar = [0 for _ in range(26)]
# 制作两个词频表
for idx, word in enumerate(stickers):
for c in word:
dicts[idx][ord(c)-ord('a')] += 1
for c in target:
tar[ord(c)-ord('a')] += 1
res = self.process(dicts, tar)
if res == float('inf'):
return -1
else:
return res
# 以词频表的形式给定当前的字符和所有贴纸，返回最小贴纸数量
def process(self, stickers, cur):
# base case: 如果当前的字符一个东西也没有了，那就是需要0张
if sum(cur)==0: # 这里有更改，词频都是0表示字符串为空
return 0
res = float('inf')
for word in stickers:
flag = 0 # 表示还没走到第一位，亦表示该位不能进入下一个子问题，即剪枝
tmp_cur = cur.copy()
for i in range(26):
if flag == 0 and tmp_cur[i] != 0 and word[i] == 0:
break # 走到第一位发现word里没有这一位，剪枝，不走了。
if flag == 0 and tmp_cur[i] != 0 and word[i] != 0:
flag = 1 # 走到第一位发现word里有这一位，可以走
if flag == 1: # 两个词频表互怼
tmp_cur[i] -= word[i]
if tmp_cur[i] < 0:
tmp_cur[i] = 0
if flag == 1:
res = min(res, self.process(stickers, tmp_cur))
if res == float('inf'):
return float('inf')
else:
return res + 1 emmm，对是对了… 超时了…
启发和联系
- 遇到那种顺序不重要的字符串，尝试考虑词频表解决一下。
- 像这种从左往右的模型，不一定有idx来表征位置，表示我从左向右处理某一个东西，本题是字符串。即我就考虑当前最左边的消除掉，但是同时也可能消除掉其他的一些，然后把剩余的传到下一个子问题。