0691-贴纸拼词

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:23 2023-09-13 16:06:23 Updated    

我们有 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.length
  • 1 <= n <= 50
  • 1 <= stickers[i].length <= 10
  • 1 <= target.length <= 15
  • stickers[i] 和 target 由小写英文单词组成

方法一：记忆化搜索 + 状态压缩

思路

记 target 的长度为 m，它一共有 2^m 个子序列（包括空子序列和 target 本身，字符相同但组成的下标不同的子序列视为不同的子序列）。根据动态规划的思路，拼出某个子序列 mask 所需要的最小贴纸数又可以由 mask 的子序列来计算，下一段介绍动态规划的思路。

在本题中，定义函数 dp}(\textit{mask}) 来求解不同状态的最小贴纸数，输入是某个子序列 mask，输出是拼出该子序列的最小贴纸数。计算拼出 mask 所需的最小贴纸数时，需要选取最优的 sticker 让其贡献部分字符，未被 sticker 覆盖的其他字符 left 需要用动态规划继续计算。在选取最优的 sticker 时，需要遍历所有 sticker。遍历到某个 sticker 时，计算 mask 和 sticker 字符的最大交集（非空），mask 中这部分交集由 sticker 贡献，剩余部分的最小贴纸数由动态规划继续计算，而 sticker 中不属于最大交集的剩下部分会被舍弃，不会产生任何贡献。遍历完所有 sticker 后，选取出所有贴纸数的最小值作为本次规划的结果，这一遍历 stickers 并根据剩余部分的最小贴纸数来计算当前 mask 的最小贴纸数的步骤完成了状态转移。边界情况是，如果 mask 为空集，则贴纸数为 0。

在动态规划时，子序列可以用一个二进制数来表示。从低位到高位，某位为 0 则表示在 target 中这一位不选取，为 1 则表示选取这一位，从而完成状态压缩的过程。代码实现上，本题解选择了记忆化搜索的方式。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int m = target.size();
        vector<int> dp(1 << m, -1);
        dp[0] = 0;
        function<int(int)> helper = [&](int mask) {
            if (dp[mask] != -1) {
                return dp[mask];
            }
            dp[mask] = m + 1;
            for (auto & sticker : stickers) {
                int left = mask;
                vector<int> cnt(26);
                for (char & c : sticker) {
                    cnt[c - 'a']++;
                }
                for (int i = 0; i < m; i++) {
                    if ((mask >> i & 1) && cnt[target[i] - 'a'] > 0) {
                        cnt[target[i] - 'a']--;
                        left ^= 1 << i;
                    }
                }
                if (left < mask) {
                    dp[mask] = min(dp[mask], helper(left) + 1);
                }
            }
            return dp[mask];
        };
        int res = helper((1 << m) - 1);
        return res > m ? -1 : res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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];
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
    public int MinStickers(string[] stickers, string target) {
        int m = target.Length;
        int[] memo = new int[1 << m];
        Array.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;
            foreach (string sticker in stickers) {
                int left = mask;
                int[] cnt = new int[26];
                for (int i = 0; i < sticker.Length; i++) {
                    cnt[sticker[i] - 'a']++;
                }
                for (int i = 0; i < target.Length; i++) {
                    char c = target[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];
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#define MIN(a, b) ((a) < (b) ? (a) : (b))

static int helper(int mask, int * dp, char ** stickers, int stickersSize, char * target) {
    int m = strlen(target);
    if (dp[mask] != -1) {
        return dp[mask];
    }
    dp[mask] = m + 1;
    for (int j = 0; j < stickersSize; j++) {
        int left = mask;
        int cnt[26];
        int len = strlen(stickers[j]);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < len; i++) {
            cnt[stickers[j][i] - 'a']++;
        }
        for (int i = 0; i < m; i++) {
            if ((mask >> i & 1) && cnt[target[i] - 'a'] > 0) {
                cnt[target[i] - 'a']--;
                left ^= 1 << i;
            }
        }
        if (left < mask) {
            dp[mask] = MIN(dp[mask], helper(left, dp, stickers, stickersSize, target) + 1);
        }
    }
    return dp[mask];
};

int minStickers(char ** stickers, int stickersSize, char * target) {
    int m = strlen(target);
    int * dp = (int *)malloc(sizeof(int) * (1 << m));
    memset(dp, -1, sizeof(int) * (1 << m));
    dp[0] = 0;
    int res = helper((1 << m) - 1, dp, stickers, stickersSize, target);
    free(dp);
    return res > m ? -1 : res;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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];
}

复杂度分析

  • 时间复杂度：O(2 ^ m \times n \times (c + m))，其中 m 为 target 的长度，c 为每个 sticker 的平均字符数。一共有 O(2 ^ m) 个状态。计算每个状态时，需要遍历 n 个 sticker。遍历每个 sticker 时，需要遍历它所有字符和 target 所有字符。

  • 空间复杂度：O(2 ^ m)，记忆化时需要保存每个状态的贴纸数量。

 Comments
On this page
0691-贴纸拼词