Rewrite of contest winner's solution


  • 4

    @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];
    }

  • 0
    Z

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


  • 0
    G

    @StefanPochmann
    Can you explain the idea or add comments to the code?


  • 0

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


  • 1
    J

    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.

  • 6
    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.


  • 1
    L

    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];
    }

  • 0

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


Log in to reply
 

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