## Stickers to Spell Word

• Time:O(2^n \cdot |\texttt{stickers}| \cdot |\texttt{stickers[i]}| \cdot n)
• Space:O(2^n)

## C++

class Solution {
public:
int minStickers(vector<string>& 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
dp[0] = 0;

continue;
// try to expand from mask by using each sticker
for (const auto& sticker : stickers) {
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)) {
break;
}
}
}

return dp.back() == INT_MAX ? -1 : dp.back();
}
};


## JAVA

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
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;

continue;
// try to expand from mask by using each sticker
for (final String sticker : stickers) {
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) {
break;
}
}
}

return dp[maxMask - 1] == Integer.MAX_VALUE ? -1 : dp[maxMask - 1];
}
}


## Python

class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
n = len(target)
# dp[i] := min # of stickers to spell out i,
# where i is the bit representation of target
dp[0] = 0

continue
# try to expand from mask by using each sticker
for sticker in stickers: