Skip to content

691. Stickers to Spell Word 👍

  • Time: $O(2^n \cdot |\texttt{stickers}| \cdot |\texttt{stickers[i]}| \cdot n)$
  • Space: $O(2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int minStickers(vector<string>& stickers, string target) {
    const int n = target.size();
    const int maxMask = 1 << n;
    // dp[i] := min # of stickers to spell out i,
    // Where i is the bit representation of target
    vector<int> dp(maxMask, INT_MAX);
    dp[0] = 0;

    for (int mask = 0; mask < maxMask; ++mask) {
      if (dp[mask] == INT_MAX)
        continue;
      // Try to expand from `mask` by using each sticker
      for (const string& sticker : stickers) {
        int superMask = mask;
        for (const char c : sticker)
          for (int i = 0; i < n; ++i)
            // Try to apply it on a missing char
            if (c == target[i] && !(superMask >> i & 1)) {
              superMask |= 1 << i;
              break;
            }
        dp[superMask] = min(dp[superMask], dp[mask] + 1);
      }
    }

    return dp.back() == INT_MAX ? -1 : dp.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int minStickers(String[] stickers, String target) {
    final int n = target.length();
    final int maxMask = 1 << n;
    // dp[i] := min # of stickers to spell out i,
    // Where i is the bit representation of target
    int[] dp = new int[maxMask];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    for (int mask = 0; mask < maxMask; ++mask) {
      if (dp[mask] == Integer.MAX_VALUE)
        continue;
      // Try to expand from `mask` by using each sticker
      for (final String sticker : stickers) {
        int superMask = mask;
        for (final char c : sticker.toCharArray())
          for (int i = 0; i < n; ++i)
            // Try to apply it on a missing char
            if (c == target.charAt(i) && (superMask >> i & 1) == 0) {
              superMask |= 1 << i;
              break;
            }
        dp[superMask] = Math.min(dp[superMask], dp[mask] + 1);
      }
    }

    return dp[maxMask - 1] == Integer.MAX_VALUE ? -1 : dp[maxMask - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def minStickers(self, stickers: List[str], target: str) -> int:
    n = len(target)
    maxMask = 1 << n
    # dp[i] := min # Of stickers to spell out i,
    # Where i is the bit representation of target
    dp = [math.inf] * maxMask
    dp[0] = 0

    for mask in range(maxMask):
      if dp[mask] == math.inf:
        continue
      # Try to expand from `mask` by using each sticker
      for sticker in stickers:
        superMask = mask
        for c in sticker:
          for i, t in enumerate(target):
            # Try to apply it on a missing char
            if c == t and not (superMask >> i & 1):
              superMask |= 1 << i
              break
        dp[superMask] = min(dp[superMask], dp[mask] + 1)

    return -1 if dp[-1] == math.inf else dp[-1]