链接：LeetCode691
给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。
你希望从自己的贴纸集合中裁剪单个字母并重新排列它们，从而拼写出给定的目标字符串 target。如果你愿意的话，你可以不止一次地使用每一张贴纸，而且每一张贴纸的数量都是无限的。拼出目标 target 所需的最小贴纸数量是多少？如果任务不可能，则返回 -1。
示例 1：
输入：
["with", "example", "science"], "thehat"
输出：
3
解释：
我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。
相关标签：备忘录+回溯
这道题也可以看成是背包问题的变形题，在背包问题中我们要求总价值最大，而这里我们要求每个字符被用完。比较简单的做法是利用回溯方法，通过备忘录记住每个字符串的最小贴纸数量，防止出现重复遍历。
需要注意的是，为了判断目标字符串用掉一个贴纸后的情况，我们可以将字符串转化为26位的数组（因为是a-z的字符，且都为小写字母，这是一种常用节省内存的做法），对数组进行“按位减”。
另外，可以利用当该贴纸没有字符串出现的第一个字符即进行抛弃等trick，进行剪枝。
其代码如下：
python:
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
n = len(stickers)
dic = {'':0}
count = [self.getCounter(sticker) for sticker in stickers]
res = self.dfs(count,target,dic)
return res if res!=float('inf') else -1
def dfs(self,count,target,dic):
if target in dic:
return dic[target]
tar = self.getCounter(target)
dic[target] = float('inf')
for i in range(len(count)):
if count[i][ord(target[0])-ord('a')]==0:continue
rest = ''
for j in range(26):
if tar[j] - count[i][j] > 0:
rest += chr(ord('a')+j) * (tar[j] - count[i][j])
dic[target] = min(dic[target],1+self.dfs(count,rest,dic))
return dic[target]
def getCounter(self,s):
res = [0 for _ in range(26)]
for ch in s:
res[ord(ch)-ord('a')]+=1
return res
C++:
class Solution {
public:
int minStickers(vector<string>& stickers, string target) {
int n = stickers.size();
vector<vector<int>> count(n,vector<int>(26,0));
for(int i=0;i<n;++i){
for(char ch:stickers[i]){
count[i][ch-'a']++;
}
}
unordered_map<string,int> mp;
mp[""]=0;
return dfs(count,target,mp);
}
int dfs(vector<vector<int>> &count,string target,unordered_map<string,int> &mp){
if(mp.count(target)) {
return mp[target];
}
vector<int> tar(26,0);
for(char ch:target){
tar[ch-'a']++;
}
mp[target] = INT_MAX;
for(int i=0;i<count.size();++i){
if(count[i][target[0]-'a'] == 0){
continue;
}
string rest = "";
for(int j=0;j<26;++j){
if(tar[j]-count[i][j]>0){
rest += string(tar[j]-count[i][j],'a'+j);
}
}
int rest_res = dfs(count,rest,mp);
if (rest_res != -1) {
mp[target] = min(mp[target],1+rest_res);
}
}
mp[target] = (mp[target]==INT_MAX?-1:mp[target]);
return mp[target];
}
};