# Explaining StefanPochmann's Rewrite of contest winner's solution & +java

• This is trying to explain @StefanPochmann 's post in here:
https://discuss.leetcode.com/topic/106368/rewrite-of-contest-winner-s-solution

1. The big idea is to use unsigned 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.
4. If not, it is -1;
``````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 subset of characters in target
vector<uint> dp(m, -1); // use index 0 - 2^n 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 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 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;
}
}
``````

Does these explanation make any sense?

• Interesting, you came up with almost the same rewrite. I thought at least my uint trick would be somewhat unique. Oh well, maybe at least my "inline if" trick is :-) (obsolete, now that attribution was added)

1. The big idea is to use unsigned number from `0` to `n^2` as bitmap to represent every `subset` of `target`;

You're not using unsigned numbers for the masks. Only for the dp values. And it's not up to `n^2` but up to `2^n`.

1. Eventually you might or might not get the ultimate result `n^2`, which is `target`, populated.

You mean `2^n - 1`?

• @StefanPochmann Hah, sorry I copied from your code and modified a bit! I thought you copied from dreamoon's solution. I hope you don't mind!

1. I removed the inline if to make it more idiot-proof, (me-proof :)
2. Yes I meant 2^n -1, good CR!!

• @StefanPochmann I thought of this approach during the contest, but this note made me rule out this approach. turns out 2^n wasn't too big.

`The time limit may be more challenging than usual. It is expected that a 50 sticker test case can be solved within 35ms on average.`

• Well, I don't mind such copying as long as it's acknowledged. Thanks for the update.

Oh, I hadn't seen that note yet. That must've gotten added shortly before the contest. It's rather strange, stating a single fixed time without differentiating between languages.

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