691. Stickers to Spell Word LeetCode Solution

In this guide, you will get 691. Stickers to Spell Word LeetCode Solution with the best time and space complexity. The solution to Stickers to Spell Word problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Stickers to Spell Word solution in C++
Stickers to Spell Word solution in Java
Stickers to Spell Word solution in Python
Additional Resources

691. Stickers to Spell Word LeetCode Solution image

Problem Statement of Stickers to Spell Word

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 string target 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.
Return the minimum number of stickers that you need to spell out target. If the task is impossible, return -1.
Note: In all test cases, all words were chosen randomly from the 1000 most common US English words, and target was chosen as a concatenation of two random words.

Example 1:

Input: stickers = [“with”,”example”,”science”], target = “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: stickers = [“notice”,”possible”], target = “basicbasic”
Output: -1
Explanation:
We cannot form the target “basicbasic” from cutting letters from the given stickers.

Constraints:

n == stickers.length
1 <= n <= 50
1 <= stickers[i].length <= 10
1 <= target.length <= 15
stickers[i] and target consist of lowercase English letters.

Complexity Analysis

Time Complexity: O(2^n \cdot |\texttt{stickers}| \cdot |\texttt{stickers[i]}| \cdot n)
Space Complexity: O(2^n)

691. Stickers to Spell Word LeetCode Solution in C++

class Solution {
 public:
  int minStickers(vector<string>& stickers, string target) {
    const int n = target.size();
    const int maxMask = 1 << n;
    // dp[i] := the minimum number of stickers to spell out i, where i is the
    // bit mask 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 letter.
            if (c == target[i] && (superMask >> i & 1) == 0) {
              superMask |= 1 << i;
              break;
            }
        dp[superMask] = min(dp[superMask], dp[mask] + 1);
      }
    }

    return dp.back() == INT_MAX ? -1 : dp.back();
  }
};
/* code provided by PROGIEZ */

691. Stickers to Spell Word LeetCode Solution in Java

class Solution {
  public int minStickers(String[] stickers, String target) {
    final int n = target.length();
    final int maxMask = 1 << n;
    // dp[i] := the minimum number of stickers to spell out i, where i is the
    // bit mask 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 letter.
            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];
  }
}
// code provided by PROGIEZ

691. Stickers to Spell Word LeetCode Solution in Python

class Solution:
  def minStickers(self, stickers: list[str], target: str) -> int:
    maxMask = 1 << len(target)
    # dp[i] := the minimum number of stickers to spell out i, where i is the
    # bit mask 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 letter.
            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]
 # code by PROGIEZ