Java DP Solution


  • 0
    R

    Similar to what the article said except I use (1<<N)-1 as the starting state.

        public int minStickers(String[] stickers, String target) {
            int nthBit = 1 << target.length();
            int[] dp = new int[nthBit];
            for (int i = 0; i < dp.length-1; i++) dp[i] = -1;
            int start = nthBit - 1;
            dp[start] = 0;
            for (int bits = start; bits > 0; bits--) {
                if (dp[bits] == -1) continue;
                for (int i = 0; i < stickers.length; i++) {
                    int currentBits = bits;
                    char[] sticker = stickers[i].toCharArray();
                    for (int j = 0; j < sticker.length; j++) {
                        char c = sticker[j];
                        int nextIndex = target.indexOf(c);
                        while (nextIndex != -1) {
                            int nextBits = 1 << nextIndex;
                            if ((nextBits & currentBits) != 0) {
                                if (dp[currentBits ^ nextBits] == -1
                                        || dp[currentBits ^ nextBits] > dp[bits] + 1) {
                                    dp[currentBits ^ nextBits] = dp[bits] + 1;
                                }
                                currentBits ^= nextBits;
                                break;
                            } else {
                                nextIndex = target.indexOf(c, nextIndex + 1);
                            }
                        }
                    }
                }
            }
            return dp[0];
        }
    

Log in to reply
 

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