## 题目描述：

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:

• `stickers` has length in the range `[1, 50]`.
• `stickers` consists of lowercase English words (without apostrophes).
• `target` has 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.

## 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;
}

}
``````

## 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]
``````

Pingbacks已关闭。