## 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 .

版权声明

本文为[Gong Shui Sanye's Diary]所创，转载请带上原文链接，感谢

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