691 贴纸拼词（记忆化搜索、状态压缩dp）

约定不等于承诺〃 2022-09-03 08:26 191阅读 0赞

**1. 问题描述：**

我们给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。你希望从自己的贴纸集合中裁剪单个字母并重新排列它们，从而拼写出给定的目标字符串 target。如果你愿意的话，你可以不止一次地使用每一张贴纸，而且每一张贴纸的数量都是无限的。拼出目标 target 所需的最小贴纸数量是多少？如果任务不可能，则返回 -1。

**示例 1：**

输入：  
\["with", "example", "science"\], "thehat"  
输出：  
3

**解释：**

我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。  
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。  
此外，这是形成目标字符串所需的最小贴纸数量。

**示例 2：**

输入：  
\["notice", "possible"\], "basicbasic"  
输出：  
\-1  
解释：  
我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

**提示：**

stickers 长度范围是 \[1，50\]。  
stickers 由小写英文单词组成（不带撇号）。  
target 的长度在 \[1，15\] 范围内，由小写字母组成。  
在所有的测试案例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选取的，目标是两个随机单词的串联。  
时间限制可能比平时更具挑战性。预计 50 个贴纸的测试案例平均可在35ms内解决。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/stickers-to-spell-word

**2. 思路分析：**

分析题目可以知道我们需要尝试所有可能的组合方案，并且在所有合法的方案中求解拼出目标值target的最小值，因为数据规模较小所以尝试使用**递归**来搜索所有可能的方案，在搜索的过程中可能会重复搜索之前已经递归求解过的状态，所以我们可以考虑记忆化搜索来解决，因为目标字符串target的长度最多为15所以我们可以使用二进制来表示所有的状态（状态最多为2 ^ 15个），状态的二进制表示中的1表示第i位的字符与目标字符串的第i位字符是匹配的，在递归的过程中记录之前已经求解过的状态，当发现之间已经求解过了那么返回求解过的值即可。在递归的时候尝试将当前贴纸对应的字符串中的字符加入到当前的状态中，只有当前字符在当前状态的对应位置是0的时候才可以添加，如果为1说明之前已经在这个位置上添加了当前字符，所以添加当前字符是无效的（没有什么贡献），后面发现可以将递归修改为状态dp，其实思路是一样的，只是将递归的形式修改为了循环的方式。

**3. 代码如下：**

**记忆化搜索：**

from typing import List
    
    
    class Solution:
        # 将当前状态cur加入当前的字符对应的状态
        def fill(self, cur: int, c: str, target: str):
            n = len(target)
            for i in range(n):
                if cur >> i & 1 == 0 and target[i] == c:
                    cur += 1 << i
                    # 匹配当前的字符之后需要break
                    break
            return cur
    
        # cur表示当前的状态, state表示记忆化列表
        def dfs(self, stickers: List[str], target: str, cur: int, state: List[int]):
            v = state[cur]
            if v != -1: return v
            # 找到了答案返回0
            if cur == (1 << len(target)) - 1: return 0
            # 因为字符串长度最大是15所以取一个比15大的数就可以了
            v = 20
            # 因为每个贴纸可以使用无限次所以在递归的时候每一次都是循环stickers的字符串表示可以使用无限次
            for s in stickers:
                t = cur
                # 填充当前的字符到当前的状态中
                for c in s:
                    t = self.fill(t, c, target)
                # 得到的当前的状态与上一个状态不一样的时候那么才往下递归
                if t != cur:
                    v = min(v, self.dfs(stickers, target, t, state) + 1)
            # 记录当前的递归结果
            state[cur] = v
            return v
    
        # 使用记忆化搜索
        def minStickers(self, stickers: List[str], target: str) -> int:
            n = len(target)
            state = [-1] * (1 << n)
            res = self.dfs(stickers, target, 0, state)
            if res == 20: res = -1
            return res

**状态压缩dp（8s多）:**

from typing import List
    
    
    class Solution:
        def minStickers(self, stickers: List[str], target: str) -> int:
            n = len(target)
            INF = 10 ** 9
            dp = [INF] * (1 << n)
            dp[0] = 0
            for state in range(1 << n):
                # 当前状态是-1的时候说明之前没有更新过当前的状态, 所以当前状态无法更新其他的状态
                if dp[state] == INF: continue
                for s in stickers:
                    t = state
                    for c in s:
                        for j in range(n):
                            if t >> j & 1 == 0 and target[j] == c:
                                t += (1 << j)
                                # 当前的字符匹配之后应该break
                                break
                    # 求解从当前状态到下一个状态的的最小值
                    dp[t] = min(dp[t], dp[state] + 1)
            res = dp[(1 << n) - 1]
            if res == INF: res = -1
            return res

**java（1s多）：**

import java.util.Arrays;
    public class Solution {
        public static int minStickers(String[] stickers, String target) {
            int n = target.length();
            int INF = 20;
            int dp[] = new int[1 << n];
            Arrays.fill(dp, INF);
            dp[0] = 0;
            for (int state = 0; state < 1 << n; ++state){
                if (state == INF) continue;
                for (String s: stickers){
                    int t = state;
                    for (int j = 0; j < s.length(); ++j){
                        char c = s.charAt(j);
                        for (int k = 0; k < n; ++k){
                            if ((t >> k & 1) == 0 && target.charAt(k) == c){
                                t += (1 << k);
                                break;
                            }
                        }
                    }
                    dp[t] = Math.min(dp[t], dp[state] + 1);
                }
            }
            int res = dp[(1 << n) - 1];
            if(res == INF) res = -1;
            return res;
        }
    }