题目描述：
LeetCode 691. Stickers to Spell Word
We are given N different types of stickers. Each sticker has a lowercase English word on it.
You would like to spell out the given target string by cutting individual letters from your collection of stickers and rearranging them.
You can use each sticker more than once if you want, and you have infinite quantities of each sticker.
What is the minimum number of stickers that you need to spell out the target? If the task is impossible, return -1.
Example 1:
Input:
["with", "example", "science"], "thehat"
Output:
3
Explanation:
We can use 2 "with" stickers, and 1 "example" sticker. After cutting and rearrange the letters of those stickers, we can form the target "thehat". Also, this is the minimum number of stickers necessary to form the target string.
Example 2:
Input:
["notice", "possible"], "basicbasic"
Output:
-1
Explanation:
We can't form the target "basicbasic" from cutting letters from the given stickers.
Note:
stickershas length in the range[1, 50].stickersconsists of lowercase English words (without apostrophes).targethas length in the range[1, 15], and consists of lowercase English letters.- In all test cases, all words were chosen randomly from the 1000 most common US English words, and the target was chosen as a concatenation of two random words.
- The time limit may be more challenging than usual. It is expected that a 50 sticker test case can be solved within 35ms on average.
题目大意：
给定一组单词stickers，目标单词target。利用stickers中的字母组成target，每个stickers的单词可以重复多次，求最小需要的stickers的单词个数。
解题思路：
解法I 记忆化搜索（Search + Memoization）
Python代码：
class Solution(object):
def minStickers(self, stickers, target):
"""
:type stickers: List[str]
:type target: str
:rtype: int
"""
cntToStr = lambda cnt: ''.join(sorted(k * v for k, v in cnt.iteritems()))
tcnt = collections.Counter(target)
scnts = [collections.Counter(s) & tcnt for s in stickers]
for x in range(len(scnts) - 1, -1, -1):
if any(scnts[x] & scnts[y] == scnts[x] for y in range(len(scnts) - 1, -1, -1) if x != y):
scnts.pop(x)
stickers = map(cntToStr, scnts)
sset = set(stickers)
dmap = {}
def search(kcnt):
key = cntToStr(kcnt)
if not key: return 0
if key in sset: return 1
if key in dmap: return dmap[key]
ans = -1
for scnt in scnts:
nkcnt = collections.Counter(kcnt)
for k in scnt:
if nkcnt[k]: nkcnt[k] -= scnt[k]
if nkcnt[k] <= 0: del nkcnt[k]
if nkcnt == kcnt: continue
val = search(nkcnt)
if val < 0: continue
if ans < 0 or val + 1 < ans: ans = val + 1
dmap[key] = ans
return ans
return search(tcnt)
Java代码：
class Solution {
private HashMap<String, Integer> dmap;
private HashMap<String, int[]> scnts;
public int[] str2Cnt(String str) {
int[] cnt = new int[26];
for (int i = 0; i < str.length(); i++) {
cnt[str.charAt(i) - 'a']++;
}
return cnt;
}
public String cnt2Str(int[] cnt) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 26; i++) {
for (int j = 0; j < cnt[i]; j++) {
sb.append('a' + i);
}
}
return sb.toString();
}
public int minStickers(String[] stickers, String target) {
dmap = new HashMap<>();
scnts = new HashMap<>();
int[] tcnt = str2Cnt(target);
for (int i = 0; i < stickers.length; i++) {
StringBuffer sb = new StringBuffer();
for (int j = 0; j < stickers[i].length(); j++) {
char ch = stickers[i].charAt(j);
if (tcnt[ch - 'a'] > 0) sb.append(ch);
}
String str = sb.toString();
if (str.length() > 0 && !scnts.containsKey(str)) {
scnts.put(str, str2Cnt(str));
}
}
return search(tcnt);
}
public int search(int[] kcnt) {
String key = cnt2Str(kcnt);
if (key.length() == 0) return 0;
if (scnts.keySet().contains(key)) return 1;
if (dmap.containsKey(key)) return dmap.get(key);
int ans = -1;
for (int[] scnt : scnts.values()) {
int[] nkcnt = kcnt.clone();
boolean stopFlag = true;
for (int i = 0; i < 26; i++) {
int nval = Math.max(0, nkcnt[i] - scnt[i]);
if (nval != nkcnt[i]) stopFlag = false;
nkcnt[i] = nval;
}
if (stopFlag) continue;
int val = search(nkcnt);
if (val < 0) continue;
if (ans < 0 || val + 1 < ans) ans = val + 1;
}
dmap.put(key, ans);
return ans;
}
}
解法II 动态规划（Dynamic Programming）
Python代码：
class Solution(object):
def minStickers(self, stickers, target):
"""
:type stickers: List[str]
:type target: str
:rtype: int
"""
dp = [0] + [-1] * ((1 << len(target)) - 1)
tcnt = collections.Counter(target)
scnts = [collections.Counter(s) & tcnt for s in stickers]
for x in range(len(scnts) - 1, -1, -1):
if any(scnts[x] & scnts[y] == scnts[x] for y in range(len(scnts) - 1, -1, -1) if x != y):
scnts.pop(x)
for status in range(1 << len(target)):
if dp[status] < 0: continue
for scnt in scnts:
nstatus = status
cnt = collections.Counter(scnt)
for i, c in enumerate(target):
if cnt[c] > 0 and status & (1 << i) == 0:
nstatus |= (1 << i)
cnt[c] -= 1
if dp[nstatus] < 0 or dp[nstatus] > dp[status] + 1:
dp[nstatus] = dp[status] + 1
return dp[-1]
本文链接：http://bookshadow.com/weblog/2017/10/08/leetcode-stickers-to-spell-word/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
