LC 691. 贴纸拼词

题目描述

这是 LeetCode 上的 691. 贴纸拼词 ，难度为困难。

我们有 $n$ 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 $-1$ 。

注意：在所有的测试用例中，所有的单词都是从 $1000$ 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。

示例 1：

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

输出：3

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

示例 2:

输入：stickers = ["notice","possible"], target = "basicbasic"

输出：-1

解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示:

$n == stickers.length$
$1 <= n <= 50$
$1 <= stickers[i].length <= 10$
$1 <= target <= 15$
stickers[i] 和 target 由小写英文单词组成

动态规划（记忆化搜索）

为了方便，我们记 $ss = stickers$，$t = target$，其中 $t$ 的长度为 $n$。

我们使用一个 $state$（一个 int 类型变量）来代表当前 $t$ 的凑成情况：若 $t[i]$ 已被凑成，则在 $state$ 中低 $i$ 位为 $1$，否则为 $0$。

起始时有 state = 0，最终若能凑成 $t$，则有 state = (1 << n) - 1。

由于每个 $ss[i]$ 可以被使用多次，因此对于一个特定的 $state$ 而言，其转换为最终的 (1 << n) - 1 的最小步数固定，因此我们可以使用「记忆化搜索」来避免对相同的 $state$ 进行重复搜索。

而在单步的搜索过程中，我们枚举每个 $ss[i]$ 来更新 $state$，假设使用某个 $ss[i]$ 得到的新状态为 $nstate$，则所有的 dfs(nstate) + 1 的最小值即是 $f[state]$。

代码：

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;
    }
}

时间复杂度：令 $n$ 和 $m$ 分别代表字符串 t 的长度和数组 ss 的长度。共有 $2^n$ 个状态，单次状态的计算复杂度为 $O(\sum_{i = 0}^{m - 1}ss[i].length \times n)$ 。整体复杂度为 $O(2^n \times \sum_{i = 0}^{m - 1}ss[i].length \times n)$
空间复杂度：$O(2^n)$

动态规划

定义 $f[state]$ 为当前 $t$ 的凑成情况为 $state$ 时，使用的最少贴纸数量。

对应的我们有 $f[0] = 0$，代表当 $t$ 的任何一位都不被凑成时，所需要的最小贴纸数量为 $0$。

每次我们尝试使用有效的状态 $s$（$f[s]$ 不为 INF 为有效状态）来更新新状态 $ns$，状态转移过程与解法一类似，每次尝试使用任意的 $ss[i]$ 来得到新的 $ns$。

代码：

class Solution {
    static int N = 15, INF = 20;
    static int[] f = new int[1 << N];
    public int minStickers(String[] ss, String t) {
        int n = ss.length, m = t.length(), mask = 1 << m;
        Arrays.fill(f, INF);
        f[0] = 0;
        for (int s = 0; s < mask; s++) {
            if (f[s] == INF) continue;
            for (String str : ss) {
                int ns = s, len = str.length();
                for (int i = 0; i < len; i++) {
                    int c = str.charAt(i) - 'a';
                    for (int j = 0; j < m; j++) {
                        if (t.charAt(j) - 'a' == c && (((ns >> j) & 1) == 0)) {
                            ns |= (1 << j);
                            break;
                        }
                    }
                }
                f[ns] = Math.min(f[ns], f[s] + 1);
            }
        }
        return f[mask - 1] == INF ? -1 : f[mask - 1];
    }
}

时间复杂度：令 $n$ 和 $m$ 分别代表字符串 t 的长度和数组 ss 的长度。共有 $2^n$ 个状态，单次状态的计算复杂度为 $O(\sum_{i = 0}^{m - 1}ss[i].length \times n)$ 。整体复杂度为 $O(2^n \times \sum_{i = 0}^{m - 1}ss[i].length \times n)$
空间复杂度：$O(2^n)$

预处理优化

在解法一和解法二的状态转移过程中，我们每次都尝试枚举所有的 $ss[i]$ 来将 $s$ 更新为 $ns$。

实际上，可以有效填充 $t$ 中尚未被占用字符的 $ss[i]$ 可能只是少数，因此我们可以先预处理每个 $ss[i]$ 到底能够提供那些字符。

在将状态 $s$ 更新为 $ns$ 时，我们只枚举那些有效的 $ss[i]$。

代码：

class Solution {
    static int N = 15, INF = 20;
    static int[] f = new int[1 << N];
    public int minStickers(String[] ss, String t) {
        int n = ss.length, m = t.length(), mask = 1 << m;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String str = ss[i];
            for (char c : str.toCharArray()) {
                int d = c - 'a';
                List<Integer> list = map.getOrDefault(d, new ArrayList<>());
                if (list.size() == 0 || list.get(list.size() - 1) != i) list.add(i);
                map.put(d, list);
            }
        }
        Arrays.fill(f, INF);
        f[0] = 0;
        for (int s = 0; s < mask; s++) {
            if (f[s] == INF) continue;
            int loc = -1;
            for (int i = 0; i < m && loc == -1; i++) {
                if (((s >> i) & 1) == 0) loc = i;
            }
            if (loc == -1) continue;
            List<Integer> list = map.getOrDefault(t.charAt(loc) - 'a', new ArrayList<>());
            for (int i = 0; i < list.size(); i++) {
                String str = ss[list.get(i)];
                int ns = s, len = str.length();
                for (int j = 0; j < len; j++) {
                    char c = str.charAt(j);
                    for (int k = 0; k < m; k++) {
                        if (t.charAt(k) == c && (((ns >> k) & 1) == 0)) {
                            ns |= (1 << k);
                            break;
                        }
                    }
                }
                f[ns] = Math.min(f[ns], f[s] + 1);
            }
        }
        return f[mask - 1] == INF ? -1 : f[mask - 1];
    }
}

时间复杂度：令 $n$ 和 $m$ 分别代表字符串 t 的长度和数组 ss 的长度。共有 $2^n$ 个状态，单次状态的计算复杂度为 $O(\sum_{i = 0}^{m - 1}ss[i].length \times n)$ 。整体复杂度为 $O(2^n \times \sum_{i = 0}^{m - 1}ss[i].length \times n)$
空间复杂度：$O(2^n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.691 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

动态规划 DFS 状态压缩二进制枚举记忆化搜索状压 DP 爆搜

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 406. 根据身高重建队列上一篇

LC 面试题 01.05. 一次编辑下一篇