You are given an array of strings called stickers, where each sticker represents a set of lowercase English letters available in unlimited supply. You are also given a string target. Your goal is to determine the minimum number of stickers required to spell out the target word.
Each sticker can be used multiple times, and you can cut individual letters from a sticker to use them. However, you cannot rearrange the letters within a sticker before using them. You must use the stickers as they are, picking letters as needed. If it is impossible to form the target using the given stickers, return -1.
Key constraints:
target cannot be formed, return -1.
At first glance, this problem looks like a variant of the "coin change" problem, where each sticker is a "coin" and we want to make up the target using as few coins as possible. A brute-force approach would try all combinations of stickers, but this quickly becomes infeasible due to the exponential number of possibilities, especially with longer targets and more stickers.
To optimize, we need to avoid redundant calculations. We notice that the problem has overlapping subproblems: for any remaining substring of target, the minimal stickers needed to complete it is the same regardless of how we reached that state. This suggests using memoization to cache results for each unique remaining target state.
Another key insight is that we can represent the state by the multiset of remaining letters needed. Each time we use a sticker, we subtract the letters it provides from the remaining letters in the target. By recursively trying all stickers and memoizing the results, we can efficiently compute the answer.
We can solve this problem using Depth-First Search (DFS) with memoization (top-down dynamic programming). Here’s how to approach it step by step:
Why use a hash map for memoization? Because the number of possible states (different combinations of remaining letters) can be large, but many will repeat. Hashing the remaining target string is an efficient way to store and look up results.
Example:
stickers = ["with", "example", "science"], target = "thehat"
The algorithm will try all combinations but, thanks to memoization, will not recompute the same "remaining" string multiple times.
Brute-force approach: The time complexity is exponential, as it tries every combination of stickers for every letter in the target. For a target of length n, the number of states is up to O(2^n).
Optimized approach (DFS + memoization):
m stickers), so the theoretical time complexity is O(m * 2^n), where n is the length of target and m is the number of stickers.
O(2^n) for the memoization table.
To solve the "Stickers to Spell Word" problem efficiently, we use a DFS with memoization strategy that models the problem as a series of subproblems: for each remaining set of letters, what is the minimum number of stickers needed? By caching results and pruning impossible paths, we avoid redundant work and ensure the solution is much faster than brute-force. This approach leverages classic dynamic programming principles and is a great example of using memoization to optimize combinatorial search problems.
from collections import Counter
from functools import lru_cache
class Solution:
def minStickers(self, stickers, target):
m = len(stickers)
sticker_counts = [Counter(sticker) for sticker in stickers]
@lru_cache(maxsize=None)
def dfs(remain):
if not remain:
return 0
res = float('inf')
remain_count = Counter(remain)
for sc in sticker_counts:
# Optimization: skip stickers that don't contain the first letter needed
if remain[0] not in sc:
continue
# Build new remaining string after using this sticker
new_remain = []
for c in remain_count:
if remain_count[c] > sc.get(c, 0):
new_remain.extend([c] * (remain_count[c] - sc.get(c, 0)))
new_remain_str = ''.join(sorted(new_remain))
tmp = dfs(new_remain_str)
if tmp != -1:
res = min(res, 1 + tmp)
return -1 if res == float('inf') else res
return dfs(''.join(sorted(target)))
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
int minStickers(vector<string>& stickers, string target) {
int m = stickers.size();
vector<vector<int>> stickerCounts(m, vector<int>(26, 0));
for (int i = 0; i < m; ++i) {
for (char c : stickers[i]) stickerCounts[i][c - 'a']++;
}
unordered_map<string, int> memo;
function<int(string)> dfs = [&](string remain) {
if (remain.empty()) return 0;
if (memo.count(remain)) return memo[remain];
vector<int> remainCount(26, 0);
for (char c : remain) remainCount[c - 'a']++;
int res = INT_MAX;
for (int i = 0; i < m; ++i) {
// Optimization: skip stickers that don't have the first needed letter
if (stickerCounts[i][remain[0] - 'a'] == 0) continue;
string newRemain;
for (int j = 0; j < 26; ++j) {
if (remainCount[j] > stickerCounts[i][j])
newRemain += string(remainCount[j] - stickerCounts[i][j], 'a' + j);
}
int tmp = dfs(newRemain);
if (tmp != -1) res = min(res, 1 + tmp);
}
memo[remain] = (res == INT_MAX) ? -1 : res;
return memo[remain];
};
sort(target.begin(), target.end());
return dfs(target);
}
};
import java.util.*;
class Solution {
public int minStickers(String[] stickers, String target) {
int m = stickers.length;
int[][] stickerCounts = new int[m][26];
for (int i = 0; i < m; ++i) {
for (char c : stickers[i].toCharArray()) {
stickerCounts[i][c - 'a']++;
}
}
Map<String, Integer> memo = new HashMap<>();
memo.put("", 0);
return dfs(stickerCounts, target, memo);
}
private int dfs(int[][] stickerCounts, String target, Map<String, Integer> memo) {
if (memo.containsKey(target)) return memo.get(target);
int[] targetCount = new int[26];
for (char c : target.toCharArray()) targetCount[c - 'a']++;
int res = Integer.MAX_VALUE;
for (int[] sticker : stickerCounts) {
// Optimization: skip stickers that don't have the first needed letter
if (sticker[target.charAt(0) - 'a'] == 0) continue;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; ++i) {
if (targetCount[i] > sticker[i]) {
for (int k = 0; k < targetCount[i] - sticker[i]; ++k) {
sb.append((char)('a' + i));
}
}
}
String newTarget = sb.toString();
int tmp = dfs(stickerCounts, newTarget, memo);
if (tmp != -1) res = Math.min(res, 1 + tmp);
}
memo.put(target, res == Integer.MAX_VALUE ? -1 : res);
return memo.get(target);
}
}
var minStickers = function(stickers, target) {
const m = stickers.length;
const stickerCounts = stickers.map(s => {
const count = Array(26).fill(0);
for (let c of s) count[c.charCodeAt(0) - 97]++;
return count;
});
const memo = {};
function dfs(remain) {
if (remain.length === 0) return 0;
if (memo[remain] !== undefined) return memo[remain];
const remainCount = Array(26).fill(0);
for (let c of remain) remainCount[c.charCodeAt(0) - 97]++;
let res = Infinity;
for (let sc of stickerCounts) {
// Optimization: skip stickers that don't have the first needed letter
if (sc[remain.charCodeAt(0) - 97] === 0) continue;
let newRemain = "";
for (let i = 0; i < 26; ++i) {
if (remainCount[i] > sc[i]) {
newRemain += String.fromCharCode(97 + i).repeat(remainCount[i] - sc[i]);
}
}
let tmp = dfs(newRemain);
if (tmp !== -1) res = Math.min(res, 1 + tmp);
}
memo[remain] = res === Infinity ? -1 : res;
return memo[remain];
}
return dfs(target.split('').sort().join(''));
};