class Solution {
public:
int minStickers(vector<string>& stickers, string target) {
}
};
691. 贴纸拼词
我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。
注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。
示例 1：
输入： stickers = ["with","example","science"], target = "thehat" 输出：3 解释： 我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。 把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。 此外，这是形成目标字符串所需的最小贴纸数量。
示例 2:
输入：stickers = ["notice","possible"], target = "basicbasic" 输出：-1 解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。
提示:
n == stickers.length1 <= n <= 501 <= stickers[i].length <= 101 <= target.length <= 15stickers[i] 和 target 由小写英文单词组成相似题目
原站题解
python3 解法, 执行用时: 76 ms, 内存消耗: 14.9 MB, 提交时间: 2023-04-11 19:36:11
'''
从target出发【起始状态】，使用每个贴纸去掉对应个数的字母【状态转移】，
看最终能否出现空字符串【目标状态】。
优化: 优先从左往右去掉当前状态中的字符，减少排列组合情况。
(比如我们删1次stickers[0]同时删1次stickers[1]，就有两个顺序达到同样的效果)
【大白话就是先删a后删b，和先删b后删a一样，我们在乎的是选了ab，而不是排列ab】
'''
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
def trans(s):
cnts = Counter()
for c in s:
if c in target:
cnts[c] += 1
return cnts
availables = [c for st in stickers if (c:=trans(st))]
queue = deque([(target, 0)])
explored = {target}
while queue:
cur, step = queue.popleft()
if not cur:
return step
for avl in availables:
if cur[0] in avl:
nxt = cur
for k, v in avl.items():
nxt = nxt.replace(k, '', v)
if nxt not in explored:
explored.add(nxt)
queue.append((nxt, step + 1))
return -1
javascript 解法, 执行用时: 400 ms, 内存消耗: 49.5 MB, 提交时间: 2023-04-11 19:35:07
/**
* @param {string[]} stickers
* @param {string} target
* @return {number}
*/
var minStickers = function(stickers, target) {
const m = target.length;
const memo = new Array(1 << m).fill(-1);
memo[0] = 0;
const res = dp(stickers, target, memo, (1 << m) - 1);
return res <= m ? res : -1;
};
const dp = (stickers, target, memo, mask) => {
const m = target.length;
if (memo[mask] < 0) {
let res = m + 1;
for (const sticker of stickers) {
let left = mask;
const cnt = new Array(26).fill(0);
for (let i = 0; i < sticker.length; i++) {
cnt[sticker[i].charCodeAt() - 'a'.charCodeAt()]++;
}
for (let i = 0; i < target.length; i++) {
const c = target[i];
if (((mask >> i) & 1) === 1 && cnt[c.charCodeAt() - 'a'.charCodeAt()] > 0) {
cnt[c.charCodeAt() - 'a'.charCodeAt()]--;
left ^= 1 << i;
}
}
if (left < mask) {
res = Math.min(res, dp(stickers, target, memo, left) + 1);
}
}
memo[mask] = res;
}
return memo[mask];
}
golang 解法, 执行用时: 112 ms, 内存消耗: 3.9 MB, 提交时间: 2023-04-11 19:34:45
func minStickers(stickers []string, target string) int {
m := len(target)
f := make([]int, 1<<m)
for i := range f {
f[i] = -1
}
f[0] = 0
var dp func(int) int
dp = func(mask int) int {
if f[mask] != -1 {
return f[mask]
}
f[mask] = m + 1
for _, sticker := range stickers {
left := mask
cnt := [26]int{}
for _, c := range sticker {
cnt[c-'a']++
}
for i, c := range target {
if mask>>i&1 == 1 && cnt[c-'a'] > 0 {
cnt[c-'a']--
left ^= 1 << i
}
}
if left < mask {
f[mask] = min(f[mask], dp(left)+1)
}
}
return f[mask]
}
ans := dp(1<<m - 1)
if ans <= m {
return ans
}
return -1
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
java 解法, 执行用时: 173 ms, 内存消耗: 41.8 MB, 提交时间: 2023-04-11 19:34:31
class Solution {
public int minStickers(String[] stickers, String target) {
int m = target.length();
int[] memo = new int[1 << m];
Arrays.fill(memo, -1);
memo[0] = 0;
int res = dp(stickers, target, memo, (1 << m) - 1);
return res <= m ? res : -1;
}
public int dp(String[] stickers, String target, int[] memo, int mask) {
int m = target.length();
if (memo[mask] < 0) {
int res = m + 1;
for (String sticker : stickers) {
int left = mask;
int[] cnt = new int[26];
for (int i = 0; i < sticker.length(); i++) {
cnt[sticker.charAt(i) - 'a']++;
}
for (int i = 0; i < target.length(); i++) {
char c = target.charAt(i);
if (((mask >> i) & 1) == 1 && cnt[c - 'a'] > 0) {
cnt[c - 'a']--;
left ^= 1 << i;
}
}
if (left < mask) {
res = Math.min(res, dp(stickers, target, memo, left) + 1);
}
}
memo[mask] = res;
}
return memo[mask];
}
}
python3 解法, 执行用时: 6420 ms, 内存消耗: 16.9 MB, 提交时间: 2023-04-11 19:34:14
# 记忆化搜索 + 状态压缩
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
m = len(target)
@cache
def dp(mask: int) -> int:
if mask == 0:
return 0
res = m + 1
for sticker in stickers:
left = mask
cnt = Counter(sticker)
for i, c in enumerate(target):
if mask >> i & 1 and cnt[c]:
cnt[c] -= 1
left ^= 1 << i
if left < mask:
res = min(res, dp(left) + 1)
return res
res = dp((1 << m) - 1)
return res if res <= m else -1