Stickers to Spell Word

Problem Statement

In this task, we are provided with several types of stickers, where each type corresponds to a sticker bearing a single lowercase English word. Our objective is to assemble a specified string, referred to as the target, by strategically extracting individual letters from an unlimited supply of these stickers. The goal is to ascertain the minimal count of stickers required to construct the target string precisely. The process involves cutting out letters from the stickers, which may then be rearranged to form the target. If it is infeasible to spell out the target using the available stickers, the output should be -1. Note that the stickers stem from a set that includes the most commonly used words in the English language, and the target itself consists of concatenated common words.

Examples

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.

Approach and Intuition

To address the problem of finding the minimum number of stickers needed to form the target string, consider the following logical steps:

1. Initial Setup:

   • Convert the list of stickers into a more usable format, such as a list of character counts for each sticker. This conversion allows for easier computation of how many of each letter each sticker can provide.

2. Dynamic Programming Approach:

   • Implement a dynamic programming technique where the state represents the current remainder of the target that needs to be formed. The value associated with each state will reflect the minimum number of stickers required to achieve that state.

3. Recursive Backtracking with Memoization:

   • Use a recursive function to try every possible combination of stickers to form the target. At each stage of recursion, attempt to use one sticker and recursively solve for the new reduced target. Additionally, store the results of previous computations in a memoization table to avoid redundant calculations.

4. Base Case and Recursion:

   • The base case for the recursion occurs when the target string is empty, meaning no stickers are needed, hence a return value of 0.
   • For each recursive call, if using a particular sticker results in forming some part of the target, recursively solve for the remaining part of the target.

5. Handling Impossible Cases:

   • If no progress can be made with any sticker (i.e., they do not help in reducing the size of the target), return an indication that forming the target is impossible with the given stickers by returning -1.

This approach meticulously considers each combination and harnesses the power of memoization to efficiently solve the problem ensuring that even larger inputs adhere to the constraints efficiently. Considerations are tuned to the need to handle scenarios where the target cannot be constructed from the provided letters, reflecting comprehensive error handling.

Solutions

class Solution {
    public int minimumStickers(String[] availableStickers, String targetWord) {
        int targetLen = targetWord.length();
        int[] dpTracker = new int[1 << targetLen];
        for (int j = 1; j < 1 << targetLen; j++) dpTracker[j] = -1;
    
        for (int currentState = 0; currentState < 1 << targetLen; currentState++) {
            if (dpTracker[currentState] == -1) continue;
            for (String sticker: availableStickers) {
                int currentStateTemp = currentState;
                for (char c: sticker.toCharArray()) {
                    for (int k = 0; k < targetLen; k++) {
                        if (((currentStateTemp >> k) & 1) == 1) continue;
                        if (targetWord.charAt(k) == c) {
                            currentStateTemp |= 1 << k;
                            break;
                        }
                    }
                }
                if (dpTracker[currentStateTemp] == -1 || dpTracker[currentStateTemp] > dpTracker[currentState] + 1) {
                    dpTracker[currentStateTemp] = dpTracker[currentState] + 1;
                }
            }
        }
        return dpTracker[(1 << targetLen) - 1];
    }
}