691 Stickers to Spell Word

691. Stickers to Spell Word

1. Question

We are given N different types of stickers. Each sticker has a lowercase English word on it.

You would like to spell out the giventargetstring by cutting individual letters from your collection of stickers and rearranging them.

You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

What is the minimum number of stickers that you need to spell out thetarget? If the task is impossible, return -1.

Example 1:

Input:

["with", "example", "science"], "thehat"

Output:

3

Explanation:

We can use 2 "with" stickers, and 1 "example" sticker.
After cutting and rearrange the letters of those stickers, we can form the target "thehat".
Also, this is the minimum number of stickers necessary to form the target string.

Example 2:

Input:

["notice", "possible"], "basicbasic"

Output:

-1

Explanation:

We can't form the target "basicbasic" from cutting letters from the given stickers.

Note:

stickershas length in the range[1, 50].

stickersconsists of lowercase English words (without apostrophes).

targethas length in the range[1, 15], and consists of lowercase English letters.

In all test cases, all words were chosen randomly from the 1000 most common US English words, and the target was chosen as a concatenation of two random words.

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.

2. Implementation

(1) Bitmap + DP

思路: 这道题很巧妙，运用了位图法和DP才能做出来。题目要求用最少的sticker得到target string。对于一个target string，它所包含的集合数为 2 ^ n。

(1) 假设target string是abc, 那么bitmap里每个subset的bit mask和所包含的character可表示为如下表格:

Subset	Bitmask
""	0
c	001
b	010
bc	011
a	100
ac	101
ab	110
abc	111

不难发现，bitmask上的1代表target string里对应的位置上的character包含在subset里

(2) 我们已经知道如何用bitmap表示target string的不同subset，接下来的问题是我们怎么知道每个subset需要最少多少个sticker？

根据动态规划的思想，我们定义dp[i]为第i个subset需要的sticker的最少数量，我们将这个数组初始化为Integer.MAXVALUE, 显然，空集合不需要任何sticker，所以有dp[0] = 0。 接着对于每个subset，我们只要遍历所有的sticker，然后对于每个sticker的每个character，我们检查target是否含有该character，如果有并且当前的subset不包含该character的话，我们将character加进subset中(通过位运算的方法mark该character已被选取)，这样我们得到一个新的subset，直到当遍历完一个sticker后，我们就知道通过现在的sticker，我们可以从开始的subset i 到达哪个一个subset，然后dp[curSet] = Math.min(dp[curSet], dp[i] + 1)

代码实现如下:

class Solution {    
    public int minStickers(String[] stickers, String target) {
        if (stickers == null || stickers.length == 0 || target == null || target.length() == 0) {
            return 0;
        }

        int n = target.length();
        // We use bitmap to represent each subset, each subset will contains different characters from target
        int m = 1 << n;
        // dp[i] means the minimum number of stickers we need to get the ith subset
        int[] dp = new int[m];
        Arrays.fill(dp, Integer.MAX_VALUE);
        // Initialize empty subset 
        dp[0] = 0;

        for (int i = 0; i < m; i++) {
            // There is no way to construct the a subset starting from the current one, so skip it
            if (dp[i] == Integer.MAX_VALUE) continue;

            for (String sticker : stickers) {
                int curSet = i;

                for (char c : sticker.toCharArray()) {
                    for (int k = 0; k < target.length(); k++) {
                        // When target contains the current character and the current subset doesn't contain the character
                        // Add that character and form a new subset
                        if (c == target.charAt(k) && ((curSet >> k) & 1) == 0) {
                            curSet |= 1 << k;
                            break;
                        }
                    }
                }
                // dp[i] + 1 means the using the minimum number of stickers to form subset i and plus one more sticker, since we 
                // can form current subset from i with one sticker
                dp[curSet] = Math.min(dp[curSet], dp[i] + 1);
            }
        }
        return dp[m - 1] == Integer.MAX_VALUE ? -1 : dp[m - 1];
    }
}

3. Time & Space Complexity

(1) Bitmap + DP: 时间复杂度O(2^n * s * l * n), n为target string的长度, s为sticker的个数, l为sticker的平均长度，空间复杂度O(2^n),