# 贴纸拼单词

描述

给出N种不同类型的贴纸。 每个贴纸上都写有一个小写英文单词。\
通过裁剪贴纸上的所有字母并重排序来拼出字符串`target`。\
每种贴纸可以使用多次，假定每种贴纸数量无限。\
拼出`target`最少需要多少张贴纸？如果不可能拼成，则返回-1。

* `stickers`的长度范围为`[1, 50]`.
* `stickers`仅由小写英文字母组成(没有撇号`'`).
* `target`的长度范围为`[1, 15]`，而且由小写字母组成。
* 在所有的测试用例中，单词是从1000个最常见的美国英文单词中任意选择的，目标单词则是由两个任意单词拼接而成。
* 时间限制可能比以往更有挑战性，期望的时间界是平均35毫秒50个测试样例。

样例

**样例 1:**

```
输入：["with", "example", "science"], "thehat"输出：3解释：使用两张"with"和一张"example"，经过裁剪和重排字母，可以得到"thehat"。这也是所需要的最少贴纸数。
```

**样例 2:**

```
输入：["notice", "possible"], "basicbasic"输出：-1解释：无法拼成"basicbasic"。
```

解题思路：

dfs+memo, 遍历可用的stickers,可重复使用sticker。从target去掉重叠字母，得到remaining word，继续dfs.

status: 剩余的单词，利用当前单词remaining\_counter = Counter(target)-Counter(sticker), 得到剩余的{remaining\_chars: count}, 组合成新单词，注意这里char可能有重复，所以需要char\*count

```
  new_remaining = ''.join(char * new_remaining_counter[char] for char in new_remaining_counter)
```

出口：remaining word为空，返回0

注意 

```python
@lru_cache(None)
```

````
```python
from typing import (
    List,
)
from collections import Counter
from functools import lru_cache  # Import lru_cache

class Solution:
    """
    @param stickers: a string array
    @param target: a string
    @return: the minimum number of stickers that you need to spell out the target
    """
    def min_stickers(self, stickers: List[str], target: str) -> int:
        # Write your code here
        sticker_counters = [Counter(i) for i in stickers]
        @lru_cache(None)
        def dp(remaining: str) -> int:
            if not remaining:
                return 0 
            min_stickers = float('inf')
            remaining_counter = Counter(remaining)
            for sticker_counter in sticker_counters:
                if sticker_counter[remaining[0]] == 0:
                    continue
                new_remaining_counter = remaining_counter-sticker_counter #需要char* 为了防止漏掉重复的char
                new_remaining = ''.join(char * new_remaining_counter[char] for char in new_remaining_counter)
                min_stickers = min(min_stickers,1+dp(new_remaining))
            return min_stickers

        result = dp(target)
        return result if result != float('inf') else -1

```
````

也可以用BFS+bit做，用target字符位置是否设置作为bit status, 存入q。 然后遍历sticker，设置target的字符位。如果当前状态已经遍历过则略过，否则存入q。当target所有位置都遍历过，则直接返回。

因为bfs层遍历，从使用一个sticker， 二个stikcer, 三个sticker。。。先到的status就是使用sticker最少的。

````
```python
from typing import (
    List,
)
from collections import deque,Counter

class Solution:
    """
    @param stickers: a string array
    @param target: a string
    @return: the minimum number of stickers that you need to spell out the target
    """
    def min_stickers(self, stickers: List[str], target: str) -> int:
        # Write your code here
        q = deque([0]) #should be a list not a set {}
        dist = {0:0}
        n = len(target)
        final_state = 1<<n # no empty space, NOT 1 >> n

        while q:
            now = q.popleft()
            for sticker in stickers:
                sticker_counter = Counter(sticker)
                state = now #should initialize to now
                for i,c in enumerate(target):
                    if not now&1<<i and sticker_counter[c] > 0:
                        state |= 1<<i
                        sticker_counter[c] -= 1
                if state in dist:
                    continue
                q.append(state)
                dist[state] = dist[now] + 1
                if state == final_state -1:
                    return dist[state]
        
        return -1




```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/meta-2024/tie-zhi-pin-dan-ci.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.