Hard

题目描述

我们有 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 中每个字符是否已被拼出。例如，对于 target = “abc”，状态 101 表示第 0 和第 2 个字符已完成。

状态转移：对于当前状态 mask，尝试使用每张贴纸，计算使用该贴纸后能达到的新状态，并更新最小步数。

优化策略：

  1. 字符过滤：只保留贴纸中在 target 中出现的字符
  2. 贴纸去重：移除被其他贴纸完全包含的贴纸
  3. 剪枝：如果当前步数已超过已知最优解，提前终止

算法流程：

  1. 预处理贴纸，统计每张贴纸的字符频次
  2. 使用 BFS 或记忆化搜索，从空状态开始搜索
  3. 对每个状态，尝试使用每张贴纸，计算新状态
  4. 当达到目标状态 (1 << target.length) - 1 时返回步数

时间复杂度主要取决于状态数量 O(2^n) 和每次转移的复杂度。

代码实现

class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = target.length();
        vector<int> dp(1 << n, -1);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == -1) continue;
            
            for (const string& sticker : stickers) {
                int newMask = mask;
                vector<int> count(26, 0);
                
                for (char c : sticker) {
                    count[c - 'a']++;
                }
                
                for (int i = 0; i < n; i++) {
                    if ((newMask & (1 << i)) == 0 && count[target[i] - 'a'] > 0) {
                        count[target[i] - 'a']--;
                        newMask |= (1 << i);
                    }
                }
                
                if (dp[newMask] == -1 || dp[newMask] > dp[mask] + 1) {
                    dp[newMask] = dp[mask] + 1;
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
};

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        n = len(target)
        dp = [-1] * (1 << n)
        dp[0] = 0
        
        for mask in range(1 << n):
            if dp[mask] == -1:
                continue
                
            for sticker in stickers:
                new_mask = mask
                count = [0] * 26
                
                for c in sticker:
                    count[ord(c) - ord('a')] += 1
                
                for i in range(n):
                    if (new_mask & (1 << i)) == 0 and count[ord(target[i]) - ord('a')] > 0:
                        count[ord(target[i]) - ord('a')] -= 1
                        new_mask |= (1 << i)
                
                if dp[new_mask] == -1 or dp[new_mask] > dp[mask] + 1:
                    dp[new_mask] = dp[mask] + 1
        
        return dp[(1 << n) - 1]

public class Solution {
    public int MinStickers(string[] stickers, string target) {
        int n = target.Length;
        int[] dp = new int[1 << n];
        Array.Fill(dp, -1);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == -1) continue;
            
            foreach (string sticker in stickers) {
                int newMask = mask;
                int[] count = new int[26];
                
                foreach (char c in sticker) {
                    count[c - 'a']++;
                }
                
                for (int i = 0; i < n; i++) {
                    if ((newMask & (1 << i)) == 0 && count[target[i] - 'a'] > 0) {
                        count[target[i] - 'a']--;
                        newMask |= (1 << i);
                    }
                }
                
                if (dp[newMask] == -1 || dp[newMask] > dp[mask] + 1) {
                    dp[newMask] = dp[mask] + 1;
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
}

var minStickers = function(stickers, target) {
    const n = target.length;
    const dp = new Array(1 << n).fill(-1);
    dp[0] = 0;
    
    for (let mask = 0; mask < (1 << n); mask++) {
        if (dp[mask]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(2^n × m × k)n为target长度，m为贴纸数量，k为贴纸平均长度
空间复杂度O(2^n)存储所有可能状态的dp数组

相关题目