题目

leetcode 691题 - 贴纸拼词
https://leetcode.com/problems/stickers-to-spell-word

给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，
目的是拼出str来返回需要至少多少张贴纸可以完成这个任务。
例子：str= ＂babac＂，arr=｛＂ba＂，＂c＂，＂abcd＂｝
至少需要两张贴纸＂ba＂和＂abcd＂，因为使用这两张贴纸，
把每一个字符单独剪开，含有2个a、2个b、1个c。是可以拼出str的。所以返回2。

题目解析

我们有 n 种不同的贴纸，每个贴纸上都有一个小写的英文单词。
我们需要拼写出一个目标字符串 target，
我们可以从收集的贴纸中切割字母并重新排列它们，且每种贴纸的数量是无限的。
我们的目标是返回拼出目标字符串所需的最小贴纸数量。
如果无法拼出目标字符串，返回 -1。

核心思想

这道题的关键是利用每个贴纸拼出目标字符串，而每个贴纸的数量是无限的，
我们可以多次使用每一种贴纸。这意味着我们需要从目标字符串中逐步去除字符，
并计算每次需要使用哪个贴纸来减少目标字符串中的字符数。

• 递归暴力解法：通过递归枚举所有贴纸，每次选择一个贴纸，减去目标字符串中可以被该贴纸覆盖的字符，递归求解剩余部分
• 动态规划解法（记忆化递归）：与递归暴力解法相同，但通过使用缓存（哈希表或数组）记录已经计算过的子问题结果，避免重复计算，优化时间复杂度。递归自顶向下，依赖于已经计算的状态。

递归暴力解法

暴力递归的思路是通过递归遍历所有可能的组合，每次选择一个贴纸，减去目标字符串中可以被该贴纸覆盖的字符，递归解决剩下的部分，直到目标字符串为空或无法拼接为止。

代码解析：

/**
 * @param stickers 所有贴纸stickers，每一种贴纸都有无穷张
 * @param target 要组成的目标
 * @return 最少张数
 */
public static int minStickers1(String[] stickers, String target) {
    int ans = process1(stickers, target);
    return ans == Integer.MAX_VALUE ? -1 : ans; // 如果没找到返回 -1，否则返回最少张数
}

public static int process1(String[] stickers, String target) {
    if (target.length() == 0) {
        return 0; // 目标字符串为空时，返回0，因为不需要任何贴纸
    }
    int min = Integer.MAX_VALUE; // 初始化最小值为无穷大
    for (String first : stickers) {
    	// 使用贴纸 first 来覆盖目标字符串 target 中的字符
        // minus 方法会返回去除掉贴纸 first 后剩余的目标字符串
        String rest = minus(target, first);
        // 如果剩下的字符串的长度发生变化，意味着贴纸 first 有效地覆盖了目标字符串的一部分
        if (rest.length() != target.length()) {
            min = Math.min(min, process1(stickers, rest)); // 递归计算剩余部分所需的最小贴纸数量
        }
    }
    // 如果找不到有效结果，返回无穷大，表示无法拼出目标字符串
    // 否则返回当前结果加1，表示再使用一个贴纸
    return min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min + 1;
}

public static String minus(String s1, String s2) {
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    // 用于统计每个字符的出现次数，长度为26，因为只有26个小写字母
    int[] count = new int[26];
    // 遍历 s1，将每个字符对应的计数增加
    for (char cha : str1) {
        count[cha - 'a']++; // 统计 s1 中每个字符的出现频率
    }
    // 减去s2中的字符频率
    for (char cha : str2) {
        count[cha - 'a']--; // 统计 s2 中每个字符的出现频率，并从 s1 的计数中减去
    }
    StringBuilder builder = new StringBuilder();
    // 遍历所有26个字母，如果某个字母在 s1 中剩余字符数大于0，则说明它还没有被完全消耗
    for (int i = 0; i < 26; i++) {
        if (count[i] > 0) {
            for (int j = 0; j < count[i]; j++) {
                builder.append((char) (i + 'a'));
            }
        }
    }
    return builder.toString(); // 返回剩余的字符串（去掉贴纸 s2 后的部分）
}

代码解析

1. process1:
   • 该方法通过递归的方式来尝试使用每一种贴纸，来减少目标字符串 target 中的字符。
   • 每次递归中，我们从 stickers 中选择一个贴纸，并通过 minus 方法计算用该贴纸覆盖后的目标字符串。
   • 如果目标字符串发生变化，说明该贴纸有效，我们继续递归求解剩余部分。
   • 最终返回最少需要的贴纸数量，如果无法拼出目标字符串，返回 Integer.MAX_VALUE。
2. minus:
   • 该方法计算目标字符串 s1 中哪些字符在贴纸 s2 的帮助下被“去掉”了，并返回去掉这些字符后的剩余字符串。
   • 利用字符频率计数器来统计每个字母在 s1 和 s2 中的出现次数，减少 s2 中的字符频率，从而得到 s1 中剩余的字符。
   • 最后将剩余的字符拼接成一个新的字符串并返回。

时间复杂度分析：

• 最坏情况：对于每个递归调用，最多需要遍历所有的贴纸和每个字符，导致指数级的时间复杂度。假设 target 长度为 m，贴纸数量为 n，每个贴纸的长度为 l，时间复杂度为 $O(n^m)$，这是一个非常高的复杂度。
• 空间复杂度：主要由递归栈空间和字符串存储占用，最坏情况下的空间复杂度为 $O(m)$，其中 m 是目标字符串的长度。

动态规划解法（记忆化递归）

为了优化暴力递归的效率，我们使用哈希表记录每个子问题的结果，
从而避免重复计算相同的子问题。通过存储已经计算过的子问题的结果，可以大大减少计算的次数。

记忆化递归：也是一种动态规划，两者的核心思想一致，区别主要体现在实现方式，
实际上是自顶向下的递归方法，它通过递归的方式计算每个子问题的解，
并使用一个缓存（通常是哈希表或数组）来记录已经计算过的子问题的解。
如果在递归过程中遇到已经计算过的子问题，就直接返回缓存中的结果，而不重新计算。
这种方法看起来像是递归实现的动态规划。

代码解析：

/**
 * @param stickers 所有贴纸stickers，每一种贴纸都有无穷张
 * @param target 要组成的目标字符串
 * @return 最少张数
 */
public static int minStickers3(String[] stickers, String target) {
    int N = stickers.length;
    int[][] counts = new int[N][26]; // counts[i]表示第i种贴纸的每个字母的出现次数（26个小写字母）
    
    // 统计每个贴纸中各字符的频率
    for (int i = 0; i < N; i++) {
        char[] str = stickers[i].toCharArray();
        for (char cha : str) {
            counts[i][cha - 'a']++; // 对于每个字符，记录它在第i种贴纸中的出现次数
        }
    }

    // dp用于存储目标字符串的最小贴纸数目
    HashMap<String, Integer> dp = new HashMap<>();
    dp.put("", 0); // 空字符串不需要任何贴纸，初始化为0
    int ans = process3(counts, target, dp); // 计算组成目标字符串的最小贴纸数

    // 如果无法组成目标字符串，则返回-1；否则返回最小张数
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

public static int process3(int[][] stickers, String t, HashMap<String, Integer> dp) {
    // 如果当前目标字符串已经计算过，直接返回结果
    if (dp.containsKey(t)) {
        return dp.get(t);
    }

    // 将目标字符串转化为字符数组，并统计每个字符的出现次数
    char[] target = t.toCharArray();
    int[] tcounts = new int[26];
    for (char cha : target) {
        tcounts[cha - 'a']++; // 统计目标字符串中每个字符的频率
    }

    int N = stickers.length;
    int min = Integer.MAX_VALUE; // 用来记录构成目标字符串所需的最小贴纸数

    // 尝试每一种贴纸
    for (int i = 0; i < N; i++) {
        int[] sticker = stickers[i];
        
        // 如果当前贴纸可以提供目标字符串中第一个字符，则尝试使用这个贴纸
        if (sticker[target[0] - 'a'] > 0) {
            StringBuilder builder = new StringBuilder();
            
            // 构建目标字符串剩余部分
            for (int j = 0; j < 26; j++) {
                if (tcounts[j] > 0) {
                    // 用当前贴纸消耗掉一部分字符后，剩下的字符数量
                    int nums = tcounts[j] - sticker[j];
                    
                    // 如果还剩下字符，加入到builder中
                    for (int k = 0; k < nums; k++) {
                        builder.append((char) (j + 'a'));
                    }
                }
            }
            String rest = builder.toString(); // 剩余的目标字符串
            // 递归调用process3计算剩余部分需要的最小贴纸数
            min = Math.min(min, process3(stickers, rest, dp)); 
        }
    }
    // 计算最终结果：如果min仍为Integer.MAX_VALUE，表示无法组成目标字符串，返回0；否则返回最小张数加1
    int ans = min + (min == Integer.MAX_VALUE ? 0 : 1); 
    // 将当前目标字符串的结果缓存到dp中，避免重复计算
    dp.put(t, ans); 
    return ans;
}

时间复杂度分析：

• 最坏情况：与暴力递归类似，但由于使用了记忆化，我们避免了重复计算。最坏情况下，时间复杂度为 $O(N\ast 26^m)$，其中 N 是贴纸数量，$26^m$ 是可能的目标字符串的状态数。
• 空间复杂度：需要使用哈希表存储子问题的结果，空间复杂度为 $O(26^m)$，其中 m 是目标字符串的长度。

小节

• 暴力递归法：。没有记忆化，容易重复计算，因此效率较低。简单易懂，但由于没有优化，时间复杂度高，适用于小规模问题。
• 记忆化递归法：通过缓存中间结果，避免重复计算，适用于大规模问题，效率更高。

时间复杂度：

• 暴力递归：$O(n^m)$，非常高，适用于小规模。
• 记忆化递归：$O(N\ast 26^m)$，更优，适用于较大规模。

空间复杂度：

• 暴力递归：$O(m)$，仅递归栈空间。
• 记忆化递归：$O(26^m)$，存储子问题的中间结果。