# 691. Sticker spelling: DFS + memorized search questions

## Title Description

This is a LeetCode Upper 691. Sticker spelling , The difficulty is difficult .

Tag : 「 Memory search 」、「DFS」、「 State compression 」、「 Explosive search 」

We have $n$ Different stickers . Each sticker has a small English word .

You want to spell the given string target , The method is to cut individual letters from the collected stickers and rearrange them . If you will , You can use each sticker multiple times , The number of each sticker is unlimited .

Back you need to spell target  Minimum number of stickers . If the task is not possible , Then return to $-1$ .

Be careful ： In all test cases , All the words are from $1000$ A random selection of the most common American English words , also target  Selected as a connection between two random words .

Example 1：

 Input ： stickers = ["with","example","science"], target = "thehat"

Output ：3

explain ：
We can use  2  individual  "with"  stickers , and  1  individual  "example"  stickers .
Cut and rearrange the letters on the sticker , You can form goals  “thehat“  了 .
Besides , This is the minimum number of stickers required to form the target string .
Copy code 

Example 2:

 Input ：stickers = ["notice","possible"], target = "basicbasic"

Output ：-1

explain ： We can't form goals by cutting the letters of a given sticker “basicbasic”.
Copy code 

Tips :

• $n == stickers.length$
• $1 <= n <= 50$
• $1 <= stickers[i].length <= 10$
• $1 <= target <= 15$
• stickers[i]  and  target  Made up of lowercase English words

## DFS + Memory search

For convenience , We remember $ss = stickers$,$t = target$, among $t$ The length of is $n$.

We use one $state$（ One int Type variable ） To represent the current $t$ The combination of ： if $t[i]$ Has been put together , It's in $state$ low $i$ Position as $1$, Otherwise $0$.

At the beginning state = 0, Finally, if we can make it $t$, Then there are state = (1 << n) - 1.

Because each $ss[i]$ Can be used many times , So for a particular $state$ for , It is converted into the final (1 << n) - 1 The minimum number of steps is fixed , So we can use 「 Memory search 」 To avoid the same $state$ Repeat the search .

And in the one-step search process , We enumerate each $ss[i]$ To update $state$, Suppose you use a $ss[i]$ The new status obtained is $nstate$, Then all of them dfs(nstate) + 1 The value of is the smallest $f[state]$.

Code ：

class Solution {
int N = 20, M = 1 << 20, INF = 50;
int[] f = new int[M];
String[] ss;
String t;
int dfs(int state) {
int n = t.length();
if (state == ((1 << n) - 1)) return 0;
if (f[state] != -1) return f[state];
int ans = INF;
for (String s : ss) {
int nstate = state;
out:for (char c : s.toCharArray()) {
for (int i = 0; i < n; i++) {
if (t.charAt(i) == c && ((nstate >> i) & 1) == 0) {
nstate |= (1 << i);
continue out;
}
}
}
if (nstate != state) ans = Math.min(ans, dfs(nstate) + 1);
}
return f[state] = ans;
}
public int minStickers(String[] stickers, String target) {
ss = stickers; t = target;
Arrays.fill(f, -1);
int ans = dfs(0);
return ans == INF ? -1 : ans;
}
}
Copy code 
• Time complexity ： Make $n$ and $m$ Each represents a string t The length and array of ss The length of . share $2^n$ Status , The computational complexity of a single state is $O(\sum_{i = 0}^{m - 1}ss[i].length \times n)$. The overall complexity is $O(2^n \times \sum_{i = 0}^{m - 1}ss[i].length \times n)$
• Spatial complexity ：$O(2^n)$

## Last

This is us. 「 Brush through LeetCode」 The first of the series No.691 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：github.com/SharingSour… .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

https://cdmana.com/2022/134/202205141227435056.html

Scroll to Top