# Rewrite of contest winner's solution

• @dreamoon's contest solution is quite nice, but it uses lots of macros. I rewrote it without them and also made it faster (about 130 ms vs 200 ms). Thanks to @feng-peng-3597 for pointing it out.

``````int minStickers(vector<string>& stickers, string target) {
int n = target.size(), N = 1 << n;
vector<uint> dp(N, -1);
dp[0] = 0;
for (int i = 0; i < N; i++) if (dp[i] != -1) {
for (string& s : stickers) {
int now = i;
for (char c : s) {
for (int r = 0; r < n; r++) {
if (target[r] == c && !((now >> r) & 1)) {
now |= 1 << r;
break;
}
}
}
dp[now] = min(dp[now], dp[i] + 1);
}
}
return dp[N-1];
}``````

• @StefanPochmann unsigned int is like a magic as both INT_MAX and -1!

• @StefanPochmann

• @gova2009 Hmm, I think it's pretty obvious. But check out @feng.peng.3597's version, which does have lots of comments.

• There are three elegant ideas I appreciate most inside this solution

1. Applying bits to represent the "status", by the help of restriction where target's size is smaller than 15. And if `i` is a subproblem of `j`, then must `i < j` holds.
2. The dp solution here is `bottom-up`, so at each turn we can check whether `dp[i] == -1` or not to skip useless status. I've written a similar solution after reading dreamoon's codes, but my version is top-down, at each turn I need to check many unreachable sub-situations.
3. Using unsigned_int, so that we can always say `"dp[now] = min(dp[now], dp[i]+1) "`, because for uint, -1 is something like INT_MAX.

1. The big idea is to use number from `0` to `2^n-1` as bitmap to represent every `subset` of `target`;
2. Then populate all of these subset from `0` to `2^n-1` by trying to apply 1 sticker at each time.
3. Eventually you might or might not get the ultimate result `2^n-1`, which is `target`, populated.
``````class Solution {
public:
int minStickers(vector<string>& stickers, string target) {
int n = target.size(), m = 1 << n; // if target has n chars, there will be m=2^n-1 subset of characters in target
vector<uint> dp(m, -1); // use index 0 - 2^n-1 as bitmaps to represent each subset of all chars of target
dp[0] = 0; // first thing we know is : dp[empty set] requires 0 stickers,
for (int i = 0; i < m; i++) { // for every subset i, start from 00000...(emptyset) to 111111...(the target)
if (dp[i] == -1) continue;
for (string& s : stickers) { // try use each sticker as an char provider to populate a super-set of i,
int sup = i;
for (char c : s) { // to do that, for each char in the sticker,
for (int r = 0; r < n; r++) {
if (target[r] == c && !((sup >> r) & 1)) { // try apply it on a missing char in the subset of target
sup |= 1 << r;
break;
}
}
}
// after you apply all possible chars in a sticker, you get an superset that take 1 extra sticker than subset
// would take, so you can try to update the superset's minsticker number with dp[sub]+1;
dp[sup] = min(dp[sup], dp[i] + 1);
}
}
return dp[m - 1]; // and the ultimate result
}
};
``````

Java

``````class Solution {
public int minStickers(String[] stickers, String target) {
int n = target.length(), m = 1 << n; // if target has n chars, there will be m=2^n-1 subset of characters in target
int[] dp = new int[m];
for (int i = 0; i < m; i++) dp[i] = Integer.MAX_VALUE; // use index 0 - 2^n-1 as bitmaps to represent each subset of all chars in target
dp[0] = 0; // first thing we know is : dp[empty set] requires 0 stickers,
for (int i = 0; i < m; i++) { // for every subset i, start from 000...000
if (dp[i] == Integer.MAX_VALUE) continue;
for (String s : stickers) { // try use each sticker as an char provider to populate 1 of its superset, to do that:
int sup = i;
for (char c : s.toCharArray()) { // for each char in the sticker, try apply it on a missing char in the subset of target
for (int r = 0; r < n; r++) {
if (target.charAt(r) == c && ((sup >> r) & 1) == 0) {
sup |= 1 << r;
break;
}
}
}
// after you apply all possible chars in a sticker, you get an superset that take 1 extra sticker than subset
// would take, so you can try to update the superset's minsticker number with dp[sub]+1;
dp[sup] = Math.min(dp[sup], dp[i] + 1);
}
}
return dp[m - 1] != Integer.MAX_VALUE ? dp[m - 1] : -1;
}
}
``````

Not sure whether these explanation make any sense.

• Rewrote few bitwise operations and variable names:

``````  public int minStickers(String[] stickers, String target) {
int n = target.length(), N = 1 << n;
int[] dp = new int[N];
Arrays.fill(dp, Integer.MAX_VALUE);

dp[0] = 0;
for (int i = 0; i < N; i++){

if (dp[i] != Integer.MAX_VALUE) {
for (String sticker : stickers) {
int status = i;
for (char c : sticker.toCharArray()) {
for (int r = 0; r < n; r++) {
int pos = 1 << r;
if (target.charAt(r) == c && (pos & status) == 0) {
status |= pos;
break;
}
}
}
dp[status] = Math.min(dp[status], dp[i] + 1);
}
}
}
return dp[N-1] == Integer.MAX_VALUE ? -1 : dp[N-1];
}``````

• @lancewang Is that a rewrite of alexander's Java one? If so, then I think my following version is a rewrite a rewrite of a rewrite of a rewrite of a rewrite :-)

``````public int minStickers(String[] stickers, String target) {
int n = target.length(), N = 1 << n;
int[] dp = new int[N];
Arrays.fill(dp, 1, N, 16);
for (int now = 0; now < N; now++)
if (dp[now] != 16)
for (String sticker : stickers) {
int next = now;
for (char c : sticker.toCharArray())
for (int r = 0; r < n; r++)
if (target.charAt(r) == c && next != (next |= 1 << r))
break;
dp[next] = Math.min(dp[next], dp[now] + 1);
}
return (dp[N-1] + 1) % 17 - 1;
}
``````

I had tried that `next != (next |= 1 << r)` earlier in C++ but couldn't get it to work. Nice to get it working in Java, saves a few of those pesky pointless `}`-lines. Edit: Oh well, I removed a few unnecessary ones (of the outermost `for` and `if`) as well, just because I can and because I hate them. Why can't every language do it like Python...

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.