LeetCode 691 - Stickers to Spell Word

Related:
LeetCode 383 - Ransom Note
LeetCode 691 - Stickers to Spell Word

https://www.cnblogs.com/grandyang/p/8468045.html

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

You would like to spell out the given target string 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 the target? 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:

• stickers has length in the range [1, 50].
• stickers consists of lowercase English words (without apostrophes).
• target has 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.

X. DP
https://leetcode.com/articles/stickers-to-spell-word/

Suppose we need dp[state] stickers to satisfy all target[i]'s for which the i-th bit of state is set. We would like to know dp[(1 << len(target)) - 1].

Algorithm

For each state, let's work with it as now and look at what happens to it after applying a sticker. For each letter in the sticker that can satisfy an unset bit of state, we set the bit (now |= 1 << i). At the end, we know now is the result of applying that sticker to state, and we update our dp appropriately.

When using Python, we will need some extra techniques from Approach #1 to pass in time.

• Time Complexity: $O(2^T * S * T)$ where $S$ be the total number of letters in all stickers, and $T$ be the number of letters in the target word. We can examine each loop carefully to arrive at this conclusion.
• Space Complexity: $O(2^T)$, the space used by dp.

public int minStickers(String[] stickers, String target) {
  int N = target.length();
  int[] dp = new int[1 << N];
  for (int i = 1; i < 1 << N; i++) dp[i] = -1;

  for (int state = 0; state < 1 << N; state++) {
      if (dp[state] == -1) continue;
      for (String sticker: stickers) {
          int now = state;
          for (char letter: sticker.toCharArray()) {
              for (int i = 0; i < N; i++) {
                  if (((now >> i) & 1) == 1) continue;
                  if (target.charAt(i) == letter) {
                      now |= 1 << i;
                      break;
                  }
              }
          }
          if (dp[now] == -1 || dp[now] > dp[state] + 1) {
              dp[now] = dp[state] + 1;
          }
      }
  }
  return dp[(1 << N) - 1];
}

https://leetcode.com/problems/stickers-to-spell-word/discuss/108334/Explaining-StefanPochmann's-Rewrite-of-contest-winner's-solution-and-%2Bjava

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;

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

http://www.zhongruitech.com/965820606.html

参考：（https://discuss.leetcode.com/topic/106368/rewrite-of-contest-winner-s-solution/7）

• 【位图法】因为待匹配串target的数量最多是15个，因此其子集的数量最多有 2^15个，而int类型占用四个字节，能够容纳标识所有target的子集。所以我们可以将target的子集 映射到 int的整型数中。
• 【int 与 target子集之间的映射关系】将int类型分解为二进制的形式后，有些位置为0，有些位置为1.表明在target中哪些位置的字符是否保留（1表示保留）。
• 【动态规划】dp中存储的是得到子集i,需要的最少的单词的数量。

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;//关键代码（下面：在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) {  //如果target中包含字符c , 并且sup中相应位置没有c。
                        sup |= 1 << r;//在sup中相应位置，加入c，形成新的集合。
                        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);//判断是否需要替换原来sup中的值。
        }
    }
    return dp[m - 1] != Integer.MAX_VALUE ? dp[m - 1] : -1;
}

这道题给了我们N个贴片，每个贴片上有一个小写字母的单词，给了我们一个目标单词target，让我们通过剪下贴片单词上的字母来拼出目标值，每个贴片都有无数个，问我们最少用几个贴片能拼出目标值target，如果不能拼出来的话，就返回-1。这道题博主最开始尝试用贪婪算法，结果发现不行，有网友留言提示说是多重背包问题，然后去论坛上看大神们的解法，果然都是用DP做的，之前曾有网友推荐过一个“背包九讲”的帖子，大概扫过几眼，真是叼到飞起啊，博主希望有时间也能总结一下。先来看这道题吧，既然是用DP来做，那么就需要用dp数组了，我们使用一个一维的dp数组，其中dp[i]表示组成第i个子集合所需要的最少的sticker的个数，注意这里是子集合，而不是子串。长度为n的字符串共有2的n次方个子集合，比如字符串"ab"，就有4个子集合，分别是 "", "a", "b", "ab"。字符串"abc"就有8个子集合，如果我们用0到7来分别对应其子集合，就有：

     abc   subset 
0    000     ""
1    001     c
2    010     b
3    011     bc
4    100     a
5    101     ac
6    110     bb
7    111     abc

我们可以看到0到7的二进制数的每一位上的0和1就相当于mask，是1的话就选上该位对应的字母，000就表示都不选，就是空集，111就表示都选，就是abc，那么只要我们将所有子集合的dp值都算出来，最后返回dp数组的最后一个位置上的数字，就是和目标子串相等的子集合啦。我们以下面这个简单的例子来讲解：

stickers = ["ab", "bc", "ac"], target = "abc"

之前说了abc的共有8个子集合，所以dp数组的长度为8，除了dp[0]初始化为0之外，其余的都初始化为INT_MAX，然后我们开始逐个更新dp数组的值，我们的目标是从sticker中取出字符，来拼出子集合，所以如果当前遍历到的dp值仍为INT_MAX的话，说明该子集合无法被拼出来，自然我们也无法再其基础上去拼别打子集合了，直接跳过。否则我们就来遍历所有的sticker，让变量cur等于i，说明此时是在第i个子集合的基础上去reach其他的子集合，我们遍历当前sticker的每一个字母，对于sticker的每个字母，我们都扫描一遍target的所有字符，如果target里有这个字符，且该字符未出现在当前cur位置的子集合中，则将该字符加入子集合中。什么意思呢，比如当前我们的cur是3，二进制为011，对应的子集合是"bc"，此时如果我们遍历到的sticker是"ab"，那么遇到"a"时，我们知道target中是有"a"的，然后我们看"bc"中包不包括"a"，判断方法是看 (cur >> k) & 1 是否为0，这可以乍看上去不太好理解，其实不难想，因为我们的子集合是跟二进制对应的，"bc"就对应着011，第一个0就表示"a"缺失，所以我们想看哪个字符，就提取出该字符对应的二进制位，提取方法就是 cur >> k，表示cur向右移动k位，懂位操作Bit Manipulation的童鞋应该不难理解，提出出来的值与上1就知道该位是0还是1了，如果是0，表示缺失，那么把该位变为1，通过 cur |= 1 << k来实现，那么此时我们的cur就变位7，二进制为111，对应的子集合是"abc"，更新此时的dp[cur]为 dp[cur] 和 dp[i] + 1 中的较大值即可，最后循环结束后，如果"abc"对应的dp值还是INT_MAX，就返回-1，否则返回其dp值

X. DP+Memoization
http://wenjiezhang.com/2017/10/22/691-Stickers-to-Spell-Word/

https://leetcode.com/problems/stickers-to-spell-word/discuss/108318/C%2B%2BJavaPython-DP-%2B-Memoization-with-optimization-29-ms-(C%2B%2B)

There are potentially a lot of overlapping sub problems, but meanwhile we don't exactly know what those sub problems are. DP with memoization works pretty well in such cases. The workflow is like backtracking, but with memoization. Here I simply use a sorted string of target as the key for the unordered_map DP. A sorted target results in a unique sub problem for possibly different strings.

dp[s] is the minimum stickers required for string s (-1 if impossible). Note s is sorted.
clearly, dp[""] = 0, and the problem asks for dp[target].

The DP formula is:

dp[s] = min(1+dp[reduced_s]) for all stickers, 
here reduced_s is a new string after certain sticker applied

Optimization: If the target can be spelled out by a group of stickers, at least one of them has to contain character target[0]. So I explicitly require next sticker containing target[0], which significantly reduced the search space.

  public int minStickers(String[] stickers, String target) {

        int m = stickers.length;
        int[][] mp = new int[m][26];
        Map<String, Integer> dp = new HashMap<>();
        for (int i = 0; i < m; i++) 
            for (char c:stickers[i].toCharArray()) mp[i][c-'a']++;
        dp.put("", 0);
        return helper(dp, mp, target);
    }
    private int helper(Map<String, Integer> dp, int[][] mp, String target) {
        if (dp.containsKey(target)) return dp.get(target);
        int ans = Integer.MAX_VALUE, n = mp.length;
        int[] tar = new int[26];
        for (char c:target.toCharArray()) tar[c-'a']++;
        // try every sticker
        for (int i = 0; i < n; i++) {
            // optimization
            if (mp[i][target.charAt(0)-'a'] == 0) continue;
            StringBuilder sb = new StringBuilder();
            // apply a sticker on every character a-z
            for (int j = 0; j < 26; j++) {
                if (tar[j] > 0 ) 
                    for (int k = 0; k < Math.max(0, tar[j]-mp[i][j]); k++)
                        sb.append((char)('a'+j));
            }
            String s = sb.toString();
            int tmp = helper(dp, mp, s);
            if (tmp != -1) ans = Math.min(ans, 1+tmp);
        }
        dp.put(target, ans == Integer.MAX_VALUE? -1:ans);
        return dp.get(target);
    }

X. BFS

https://leetcode.com/problems/stickers-to-spell-word/discuss/108315/java-BFS-solution

public int minStickers(String[] stickers, String target) {
    // lower case
    if (target.length() == 0) return 0;
    int ns = stickers.length;
    int tl = target.length();
    int[][] letters = new int[ns][26];
    for (int i = 0; i < stickers.length; i++) {
        String s = stickers[i];
        for (char c : s.toCharArray()) {
            letters[i][c - 'a']++;
        }
    }

    int[] targetLetters = new int[26];
    for (char c : target.toCharArray()) {
        targetLetters[c - 'a']++;
    }

    int level = 0;
    Deque<int[]> queue = new LinkedList<>();
    Set<String> set = new HashSet<>();
    queue.offerFirst(targetLetters);

    while (!queue.isEmpty()) {
        int size = queue.size();
        level++;
        for (int i = 0; i < size; i++) {
            int[] cur = queue.pollLast();
            String curKey = toKey(cur);
            if (set.add(curKey)) {
                for (int j = 0; j < letters.length; j++) {
                    if (letters[j][curKey.charAt(0) - 'a'] == 0) continue;
                    int[] curtarget = cur.clone();
                    for (int k = 0; k < 26; k++) {
                        int left = curtarget[k] - letters[j][k];
                        curtarget[k] =  left > 0 ? left : 0;
                    }
                    String temp = toKey(curtarget);
                    if (temp.length() == 0) return level;
                    queue.offerFirst(curtarget.clone());
                } 
            }
        }
    }
    return -1;
}
private String toKey(int[] arr) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < arr[i]; j++) {
            sb.append((char)('a' + i));
        }
    }
    return sb.toString();
}




X. Optimized Exhaustive Search: DFS
https://leetcode.com/problems/stickers-to-spell-word/discuss/207904/Java-Backtracking-Solution-with-explanation

/* (1) keep an character indexed array for all characters we have at hand...
 * (2) traverse each character of the target, if we have the character in out charcter array... 
 *     just remove it from the array, and go to check the character at next position
 * (3) if we don't have the character at hand...
 *     we will traverse the sticker, find a word that contains that character, increment the number of stiker used 
 *     and update the array of character available
 * (4) we can simplify step (3) by doing some preprocess of the sticker array, create a charcter-indexed count array for each word in
 *     that array
 */
    int[][] countMap; //map[i][j] means the number of character (j + 'a') contains in the ith element of stickers...
    int cnt = Integer.MAX_VALUE;
    public int minStickers(String[] stickers, String target) {
        if (target == null) return -1;
        if (target.length() == 0) return 0;
        if (stickers == null || stickers.length == 0) return -1;
        
        int m = stickers.length;
        countMap = new int[m][26];
        
        for (int i = 0; i < stickers.length; i++) {
            String s = stickers[i];
            for (char c : s.toCharArray()) {
                countMap[i][c - 'a']++;
            }
        }
        count(0, 0, new int[26], target, stickers);
        return cnt == Integer.MAX_VALUE ? -1 : cnt;
    }
    
    private void count(int curCnt, int pos, int[] charAvailable, String target, String[] stickers) {
        if (curCnt >= cnt) return; //prune the search, when curCnt will be larger then cnt...
        //important step... other wise will get TLE..
        int m = stickers.length, n = target.length();
        if (pos == n) {
            cnt = Math.min(cnt, curCnt);
            return;
        }
        char c = target.charAt(pos);
        if (charAvailable[c - 'a'] > 0) {
            charAvailable[c - 'a']--;
            count(curCnt, pos + 1, charAvailable, target, stickers);
            charAvailable[c - 'a']++;
        } else {
            for (int i = 0; i < m; i++) {
                if (countMap[i][c - 'a'] == 0) continue;
                for(int j = 0; j < 26; j++) {
                    charAvailable[j] += countMap[i][j];
                }
                count(curCnt + 1, pos, charAvailable, target, stickers);
                for(int j = 0; j < 26; j++) {
                    charAvailable[j] -= countMap[i][j];
                }
            }
        }  
    }




https://leetcode.com/articles/stickers-to-spell-word/

• Time Complexity: Let $N$ be the number of stickers, and $T$ be the number of letters in the target word. A bound for time complexity is $O(N^{T+1} T^2)$: for each sticker, we'll have to try using it up to $T+1$times, and updating our target count costs $O(T)$, which we do up to $T$ times. Alternatively, since the answer is bounded at $T$, we can prove that we can only search up to $\binom{N+T-1}{T-1}$ times. This would be $O(\binom{N+T-1}{T-1} T^2)$.
• Space Complexity: $O(N+T)$, to store stickersCount, targetCount, and handle the recursive callstack when calling search.

int best;
int[][] stickersCount;
int[] targetCount;

public void search(int ans, int row) {
    if (ans >= best) return;
    if (row == stickersCount.length) {
        for (int c: targetCount) if (c > 0) return;
        best = ans;
        return;
    }

    int used = 0;
    for (int i = 0; i < stickersCount[row].length; i++) {
        if (targetCount[i] > 0 && stickersCount[row][i] > 0) {
            used = Math.max(used, (targetCount[i] - 1) / stickersCount[row][i] + 1);
        }
    }
    for (int i = 0; i < stickersCount[row].length; i++) {
        targetCount[i] -= used * stickersCount[row][i];
    }

    search(ans + used, row + 1);
    while (used > 0) {
        for (int i = 0; i < stickersCount[row].length; i++) {
            targetCount[i] += stickersCount[row][i];
        }
        used--;
        search(ans + used, row + 1);
    }
}

public int minStickers(String[] stickers, String target) {
    int[] targetNaiveCount = new int[26];
    for (char c: target.toCharArray()) targetNaiveCount[c - 'a']++;

    int[] index = new int[26];
    int t = 0;
    for (int i = 0; i < 26; i++) {
        if (targetNaiveCount[i] > 0) {
            index[i] = t++;
        } else {
            index[i] = -1;
        }
    }

    targetCount = new int[t];
    t = 0;
    for (int c: targetNaiveCount) if (c > 0) {
        targetCount[t++] = c;
    }

    stickersCount = new int[stickers.length][t];
    for (int i = 0; i < stickers.length; i++) {
        for (char c: stickers[i].toCharArray()) {
            int j = index[c - 'a'];
            if (j >= 0) stickersCount[i][j]++;
        }
    }

    int anchor = 0;
    for (int i = 0; i < stickers.length; i++) {
        for (int j = anchor; j < stickers.length; j++) if (j != i) {
            boolean dominated = true;
            for (int k = 0; k < t; k++) {
                if (stickersCount[i][k] > stickersCount[j][k]) {
                    dominated = false;
                    break;
                }
            }

            if (dominated) {
                int[] tmp = stickersCount[i];
                stickersCount[i] = stickersCount[anchor];
                stickersCount[anchor++] = tmp;
                break;
            }
        }
    }

    best = target.length() + 1;
    search(0, anchor);
    return best <= target.length() ? best : -1;
}

LeetCode Live: 691 Stickers to Spell Word, 05/15/2019