• 贴纸拼词问题

    贴纸拼词问题

    作者：Grey

    原文地址:

    博客园：贴纸拼词问题

    CSDN：贴纸拼词问题

    题目描述

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

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

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

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

    题目链接：LeetCode 691. Stickers to Spell Word

    暴力解法

    定义递归函数

    int process(String[] stickers, String target)

    • 1

    递归含义表示：stickers 作为贴纸数组，可以拼凑出 target 字符串的最小贴纸数量是多少。，如果无论如何都无法拼凑出 target，则返回无穷大，即：Integer.MAX_VALUE

    接下来是 base case，如果 target 为空串，直接返回 0，表示无须任何贴纸就可以组成，即

            if (target.length() == 0) {
            // 目标是空串，只需要0张贴纸
            return 0;
        }

    • 1
    • 2
    • 3
    • 4

    接下来是普遍情况，枚举 stickers 中每一个字符串 s，将 s 中包含的所有字符从 target 移除掉，然后看 target 剩下哪些字符，继续被 stickers 中的字符分解。

    定义一个工具函数

    String minus(String first, String target)

    • 1

    这个函数实现的功能就是：将 first 中包含的所有字符从 target 移除掉，然后看 target 剩下哪些字符，把剩下的字符按字典序排序后的结果字符串返回。

    例如，first = “with”， target = “thehat”，target 移除掉 first 中的所有字符以后，得到 “aeht” （按字典序从小到大排序后）。

    minus 方法如下

        private static String minus(String first, String target) {
        char[] s2 = target.toCharArray();
        char[] s1 = first.toCharArray();
        StringBuilder sb = new StringBuilder();
        int[] dict = new int[26];
        for (char c : s2) {
            dict[c - 'a']++;
        }
        for (char c : s1) {
            dict[c - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            int times = dict[i];
            for (int m = 0; m < times; m++) {
                sb.append((char) (i + 'a'));
            }
        }
        return sb.toString();
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    暴力解法完整代码如下

    class Solution {
    public static int minStickers(String[] stickers, String target) {
        if (stickers == null || stickers.length < 1 || target.length() < 1) {
            return 0;
        }
        int p = process(stickers, target);
        return p == Integer.MAX_VALUE ? -1 : p;
    }

    public static int process(String[] stickers, String target) {
        if (target.length() == 0) {
            // 目标是空串，只需要0张贴纸
            return 0;
        }
        int ways = Integer.MAX_VALUE;
        for (String s : stickers) {
            String rest = minus(s, target);
            if (target.length() != rest.length()) {
                // 有效
                ways = Math.min(process(stickers, rest), ways);
            }
        }
        return ways == Integer.MAX_VALUE ? Integer.MAX_VALUE : ways + 1;
    }

    private static String minus(String first, String target) {
        char[] s2 = target.toCharArray();
        char[] s1 = first.toCharArray();
        StringBuilder sb = new StringBuilder();
        int[] dict = new int[26];
        for (char c : s2) {
            dict[c - 'a']++;
        }
        for (char c : s1) {
            dict[c - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            int times = dict[i];
            for (int m = 0; m < times; m++) {
                sb.append((char) (i + 'a'));
            }
        }
        return sb.toString();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    超时

    image

    上述暴力过程，可以做一些优化，比如

    stickers 数组是字符串数组，可以转换成整型二维数组来表示

            int[][] st = new int[stickers.length][26];
        for (int i = 0; i < stickers.length; i++) {
            String sticker = stickers[i];
            char[] chars = sticker.toCharArray();
            for (char c : chars) {
                st[i][c - 'a']++;
            }
        }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    其中st[i]就是一个一维数组，表示 stickers[i] 这个字符串，

    st[i][x] 存的就是 stickers[i] 这个字符串在 x 号位置的字符减去’a’的 ASCII 码值。

    比如 stickers[i] == “abbc”，那么 st[i] = {0,1,1,2}。

    经过上述初始化，递归过程中的循环枚举 stickers 中字符串的过程，就可以做剪枝

            for (int[] first : stickers) {
            if (first[cs[0] - 'a'] > 0) {
                // 包含target首字母的字符串才考虑尝试
                String rest = minus(first, cs);
                if (rest.length() != target.length()) {
                    ans = Math.min(p2(stickers, rest), ans);
                }
            }
        }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    其中if (first[cs[0] - 'a'] > 0)这个条件就是只考虑包含 target 首字母的的字符串才做尝试，因为 target 的首字符一定要被消除，所以先消除和后消除没差别。

    经过上述优化的完整代码如下

    class Solution {
    public static int minStickers(String[] stickers, String target) {
        if (stickers == null || stickers.length < 1 || target.length() < 1) {
            return 0;
        }
        int[][] st = new int[stickers.length][26];
        for (int i = 0; i < stickers.length; i++) {
            String sticker = stickers[i];
            char[] chars = sticker.toCharArray();
            for (char c : chars) {
                st[i][c - 'a']++;
            }
        }
        int res = p2(st, target);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public static int p2(int[][] stickers, String target) {
        if (target.length() == 0) {
            return 0;
        }
        char[] cs = target.toCharArray();
        int ans = Integer.MAX_VALUE;
        for (int[] first : stickers) {
            if (first[cs[0] - 'a'] > 0) {
                // 包含target首字母的字符串才考虑尝试
                String rest = minus(first, cs);
                if (rest.length() != target.length()) {
                    ans = Math.min(p2(stickers, rest), ans);
                }
            }
        }
        return ans == Integer.MAX_VALUE ? Integer.MAX_VALUE : ans + 1;
    }

    public static String minus(int[] first, char[] target) {
        int[] count = new int[first.length];
        System.arraycopy(first, 0, count, 0, first.length);
        StringBuilder sb = new StringBuilder();
        for (char c : target) {
            if (count[c - 'a'] > 0) {
                count[c - 'a']--;
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    超时

    image

    使用动态规划中的缓存法 （可 AC）

    在暴力递归中，增加一个参数 Map map, 其中 key 是 target 字符串，value 是组成这个 target 字符串要耗费的最少贴纸数量，在递归函数中，增加如下逻辑

            if (map.containsKey(target)) {
            return map.get(target);
        }
        if (target.length() == 0) {
            map.put(target, 0);
            return 0;
        }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    遍历 stickers 得到最少字符串的时候，把结果加入这个哈希表，

     map.put(target, ways);

    • 1

    即可。

    完整代码如下

    class Solution {
    public static String minus(int[] first, char[] target) {
        int[] count = new int[first.length];
        System.arraycopy(first, 0, count, 0, first.length);
        StringBuilder sb = new StringBuilder();
        for (char c : target) {
            if (count[c - 'a'] > 0) {
                count[c - 'a']--;
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }

    // 将字符串数组转换成二维数组
    public static int[][] build2D(String[] stickers) {
        int n = stickers.length;
        int[][] s = new int[n][26];
        for (int i = 0; i < n; i++) {
            char[] line = stickers[i].toCharArray();
            for (char c : line) {
                s[i][c - 'a']++;
            }
        }
        return s;
    }

    // 增加缓存
    // 可以AC
    public static int minStickers(String[] stickers, String target) {
        if (target == null || target.length() < 1) {
            return 0;
        }
        Map<String, Integer> map = new HashMap<>();
        map.put("", 0);
        int res = p3(build2D(stickers), target, map);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public static int p3(int[][] stickers, String target, Map<String, Integer> map) {
        if (map.containsKey(target)) {
            return map.get(target);
        }
        if (target.length() == 0) {
            map.put(target, 0);
            return 0;
        }
        char[] t = target.toCharArray();
        int ways = Integer.MAX_VALUE;
        // 每一张贴纸作为第一张贴纸，搞定后续的方法数
        for (int[] first : stickers) {
            // 搞定第一个字符的的贴纸才考虑后续过程
            if (first[t[0] - 'a'] > 0) {
                String rest = minus(first, t);
                // rest长度==target长度，说明没有搞定任何情况
                if (rest.length() != target.length()) {
                    ways = Math.min(p3(stickers, rest, map), ways);
                }
            }
        }
        ways = ways == Integer.MAX_VALUE ? Integer.MAX_VALUE : ways + 1;
        map.put(target, ways);
        return ways;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66

    更多

    算法和数据结构笔记

  • 相关阅读:
    李宏毅机器学习课程笔记（更新ing）
    75. 颜色分类（中等 数组 双指针 排序）
    煤炭行业数据库-煤炭价格、消耗量、发电量&分省市民用电、工业用电数据
    C++day5
    Nginx编译安装+监控模块vts
    伪原创工具-好用的伪原创软件有哪些特征
    [大模型]QAnything纯Python环境安装教程
    LeetCode题目笔记——6228. 距离字典两次编辑以内的单词
    数字藏品平台的企业需要准备哪些资质证书？
    视频分析：走路看手机行为
  • 原文地址：https://blog.csdn.net/hotonyhui/article/details/127622638