# 691. Stickers to Spell Word        • Time: $O(2^n \cdot |\texttt{stickers}| \cdot |\texttt{stickers[i]}| \cdot n)$
• Space: $O(2^n)$
  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 class Solution { public: int minStickers(vector& stickers, string target) { const int n = target.size(); const int maxMask = 1 << n; // dp[i] := min # of stickers to spell out i, // Where i is the bit representation of target vector dp(maxMask, INT_MAX); dp = 0; for (int mask = 0; mask < maxMask; ++mask) { if (dp[mask] == INT_MAX) continue; // Try to expand from mask by using each sticker for (const string& sticker : stickers) { int superMask = mask; for (const char c : sticker) for (int i = 0; i < n; ++i) // Try to apply it on a missing char if (c == target[i] && !(superMask >> i & 1)) { superMask |= 1 << i; break; } dp[superMask] = min(dp[superMask], dp[mask] + 1); } } return dp.back() == INT_MAX ? -1 : dp.back(); } }; 
  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 class Solution { public int minStickers(String[] stickers, String target) { final int n = target.length(); final int maxMask = 1 << n; // dp[i] := min # of stickers to spell out i, // Where i is the bit representation of target int[] dp = new int[maxMask]; Arrays.fill(dp, Integer.MAX_VALUE); dp = 0; for (int mask = 0; mask < maxMask; ++mask) { if (dp[mask] == Integer.MAX_VALUE) continue; // Try to expand from mask by using each sticker for (final String sticker : stickers) { int superMask = mask; for (final char c : sticker.toCharArray()) for (int i = 0; i < n; ++i) // Try to apply it on a missing char if (c == target.charAt(i) && (superMask >> i & 1) == 0) { superMask |= 1 << i; break; } dp[superMask] = Math.min(dp[superMask], dp[mask] + 1); } } return dp[maxMask - 1] == Integer.MAX_VALUE ? -1 : dp[maxMask - 1]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def minStickers(self, stickers: List[str], target: str) -> int: n = len(target) maxMask = 1 << n # dp[i] := min # Of stickers to spell out i, # Where i is the bit representation of target dp = [math.inf] * maxMask dp = 0 for mask in range(maxMask): if dp[mask] == math.inf: continue # Try to expand from mask by using each sticker for sticker in stickers: superMask = mask for c in sticker: for i, t in enumerate(target): # Try to apply it on a missing char if c == t and not (superMask >> i & 1): superMask |= 1 << i break dp[superMask] = min(dp[superMask], dp[mask] + 1) return -1 if dp[-1] == math.inf else dp[-1]