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


  • 1

    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?


  • 0

    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?


  • 0

    @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!!

  • 0

    @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.


  • 0

    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.


Log in to reply
 

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