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.length1 <= n <= 501 <= stickers[i].length <= 101 <= target.length <= 15stickers[i] and target consist of lowercase English letters.This approach utilizes recursive backtracking in combination with memoization to solve the problem. The idea is to maintain a count of letters that are still needed to complete the target string and recursively explore combinations of stickers that reduce this count. Memoization helps in caching previously computed results for specific target states, avoiding redundant calculations.
The steps are as follows:
This Python solution utilizes a recursive function with memoization to determine the minimum number of stickers needed. It preprocesses each sticker to count letter frequencies and applies DFS to explore useful sticker combinations. Memoization caches results for recurring target patterns, efficiently solving overlapping subproblems.
Time Complexity: O(T * 2^T * S), where T is the length of the target, and S is the number of stickers. This accounts for checking each subset of the target matched with each sticker.
Space Complexity: O(T * k), where k is the average word length in stickers, for the memoization storage.
In this approach, a depth-first search (DFS) strategy is employed, utilizing bitmasking to represent the state of the target string. Each bit corresponds to a character position in the target, and a bit set to 1 indicates that a letter is needed. This makes it efficient to track state transitions and reuse computed outcomes using a bitmask.
The bitmask representation simplifies target state management, especially with small problems like this one where all state combinations fit comfortably in integer bit representation.
The solution implemented in Java leverages bitmasking along with a memoization HashMap to efficiently calculate the minimum number of stickers required. The helper function explores possible sticker applications iteratively, adjusting the target state and caching results to avoid redundant calculations.
Time Complexity: O(2^T * n * T), where T is the target length and n the number of stickers, reflecting operations per state per sticker.
Space Complexity: O(2^T + n), for the dp table managing the state combinations and sticker reading.
A Depth First Search (DFS) approach combined with memoization can efficiently solve this problem. By recursively exploring each possible configuration of using stickers to form the target and caching results for already computed subproblems, we minimize redundant calculations.
The idea is to count the frequency of each character needed for the target and use it to explore different combinations of stickers. We process stickers in such a way that each branch of our recursive call attempts to use the result of one sticker to reduce the requirement for the remaining target. Memoization is used to store results for target states we've already calculated for.
This Python solution utilizes DFS with memoization to navigate possible sticker usage combinations recursively. The Counter from the collections module is used to manage and compare character frequencies efficiently. A nested function dfs() handles the recursions, checking if a given state of the target string has been computed before or if it can be completed with the current stickers. If a target can be formed, it records the minimum number of stickers required.
Java
Time Complexity: O(2^T * N * L), where T is the length of the target, N is the number of stickers, and L is the average length of a sticker.
Space Complexity: O(T), for the memoization cache.
This approach uses dynamic programming with bit masking to keep track of which characters in the target have been fulfilled. The idea is to use a bit mask to represent the completeness of parts of the target. Each bit in the mask represents whether a character in the target has been used or not.
By iterating over each sticker, we apply the possible contribution of each sticker to partially fulfill the target (indicated by updating the bitmask). A DP array helps record the minimum sticker usage to reach any given bitmap state of the target.
This C++ solution employs a dynamic programming approach with bitmasking. The DP array keeps track of the minimum number of stickers required to attain various states of completeness of the target string, which are represented via bit masks. Each state explores how stickers can contribute to completing the target, and bit masking efficiently labels which parts are completed or pending.
C#
Time Complexity: O(N * T * 2^T), where T is the length of the target, N is the number of stickers.
Space Complexity: O(2^T), for the DP array.
| Approach | Complexity |
|---|---|
| Recursive Backtracking with Memoization | Time Complexity: O(T * 2^T * S), where T is the length of the target, and S is the number of stickers. This accounts for checking each subset of the target matched with each sticker. Space Complexity: O(T * k), where k is the average word length in stickers, for the memoization storage. |
| DFS and Bitmasking Optimization | Time Complexity: O(2^T * n * T), where T is the target length and n the number of stickers, reflecting operations per state per sticker. Space Complexity: O(2^T + n), for the dp table managing the state combinations and sticker reading. |
| DFS with Memoization | Time Complexity: O(2^T * N * L), where T is the length of the target, N is the number of stickers, and L is the average length of a sticker. |
| Bit-Masked Dynamic Programming | Time Complexity: O(N * T * 2^T), where T is the length of the target, N is the number of stickers. |
Word Search - Backtracking - Leetcode 79 - Python • NeetCode • 380,746 views views
Watch 9 more video solutions →Practice Stickers to Spell Word with our built-in code editor and test cases.
Practice on FleetCode