贴纸拼词

/*
 * 问题描述：给定若干个贴纸，每个贴纸上都有一个单词，目标是使用最少的贴纸拼出给定的目标字符串。
 * 题解思路：
 * 1. 统计目标字符串中每个字符的出现次数。
 * 2. 使用动态规划来记录每个状态所需的最小贴纸数量。
 * 3. 状态用一个整数表示，二进制中的每一位表示目标字符串中对应字符的是否已被满足。
 * 4. 使用Java Stream简化遍历过程。
 */
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
 
public class StickersToSpellWordStream {
    public int minStickers(String[] stickers, String target) {
        int n = target.length();
        int[] dp = new int[1 << n];
        IntStream.range(0, dp.length).forEach(i -> dp[i] = Integer.MAX_VALUE);
        dp[0] = 0;
 
        IntStream.range(0, dp.length).forEach(state -> {
            if (dp[state] == Integer.MAX_VALUE) return;
            for (String sticker : stickers) {
                int nextState = state;
                int[] count = new int[26];
                sticker.chars().forEach(c -> count[c - 'a']++);
                IntStream.range(0, target.length()).forEach(i -> {
                    char c = target.charAt(i);
                    if ((state >> i & 1) == 1) return;  // already satisfied
                    if (count[c - 'a'] > 0) {
                        count[c - 'a']--;
                        nextState |= (1 << i);
                    }
                });
                dp[nextState] = Math.min(dp[nextState], dp[state] + 1);
            }
        });
 
        return dp[(1 << n) - 1] == Integer.MAX_VALUE ? -1 : dp[(1 << n) - 1];
    }
}