贴纸拼单词

https://www.lintcode.com/problem/1081/?utm_source=sc-libao-ql

描述

给出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

注意

@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




```