LWC 53:691. Stickers to Spell Word

LWC 53:691. Stickers to Spell Word

传送门:691. Stickers to Spell Word

Problem:

We are given N different types of stickers. Each sticker has a lowercase English word on it. You would like to spell out the given target string by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker. What is the minimum number of stickers that you need to spell out the target? If the task is impossible, return -1.

Example 1:

Input: [“with”, “example”, “science”], “thehat” Output: 3 Explanation: We can use 2 “with” stickers, and 1 “example” sticker. After cutting and rearrange the letters of those stickers, we can form the target “thehat”. Also, this is the minimum number of stickers necessary to form the target string.

Example 2:

Input: [“notice”, “possible”], “basicbasic” Output: -1 Explanation: We can’t form the target “basicbasic” from cutting letters from the given stickers.

Note:

stickers has length in the range [1, 50]. stickers consists of lowercase English words (without apostrophes). target has length in the range [1, 15], and consists of lowercase English letters. In all test cases, all words were chosen randomly from the 1000 most common US English words, and the target was chosen as a concatenation of two random words. The time limit may be more challenging than usual. It is expected that a 50 sticker test case can be solved within 35ms on average.

思路: 因为字母顺序无关,所以只需要统计target中每个字母出现的次数,接着对于给定的stickers,如果选择了某个sticker(当然你也可以不选),那么就从target中减去共同出现的字母频次(以sticker为准),这样一来,该问题就变成了重复子问题。

代码如下:

    static final int INF = 0x3f3f3f3f;
    Map<String, Integer> mem = new HashMap<>();

    int f(String target, int n) {
        if (mem.containsKey(target)) return mem.get(target);

        int[] tar = preprocess(target);
        int ans = INF;
        for (int i = 0; i < n; ++i) {

            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < 32; ++j) {
                if (tar[j] > 0) {
                    for (int k = 1; k <= Math.max(0, tar[j] - sticker_map[i][j]); ++k) {
                        sb.append((char)(j + 'a'));
                    }
                }
            }

            String sub = sb.toString();

            if (sub.length() != target.length()) {
                ans = Math.min(ans, f(sub, n) + 1);
            }
        }
        mem.put(target, ans);
        return ans;
    }

    int[][] sticker_map;
    public int minStickers(String[] stickers, String target) {
        if (judge(stickers, target)) return -1;
        int n = stickers.length;
        sticker_map = new int[n][32];
        for (int i = 0; i < n; ++i) {
            sticker_map[i] = preprocess(stickers[i]);
        }
        mem.put("", 0);
        return f(target, n);
    }

    boolean judge(String[] stickers, String target) {
        int[] map = new int[32];
        for (char c : target.toCharArray()) {
            if (map[c - 'a'] == 0)
                map[c - 'a']++;
        }
        for (String s : stickers) {
            for (char c : s.toCharArray()) map[c - 'a'] --;
        }

        for (int i = 0; i < 32; ++i) {
            if (map[i] >= 1) return true;
        }
        return false;
    }

    int[] preprocess(String target) {
        int[] map = new int[32];
        for (char c : target.toCharArray()) map[c - 'a']++;
        return map;
    }

实际上是状态压缩DP,采用BOTTOM-UP,代码如下:

    public int minStickers(String[] stickers, String target) {
        int N = target.length();
        int[] dp = new int[1 << N];

        for (int i = 1; i < 1 << N; ++i) dp[i] = -1;

        for (int state = 0; state < 1 << N; ++state) {
            if (dp[state] == -1) continue;
            for (String sticker : stickers) {
                int now = state;
                for (char c : sticker.toCharArray()) {
                    for (int i = 0; i < N; ++i) {
                        if (((now >> i) & 1) == 1) continue;
                        if (c == target.charAt(i)) {
                            now |= 1 << i;
                            break;
                        }
                    }
                }

                if (dp[now] == -1 || dp[now] > dp[state] + 1) {
                    dp[now] = dp[state] + 1;
                }
            }
        }

        return dp[(1 << N) - 1];
    }

从递归的版本可以看出,前后状态发生变化的实际是target,HashMap记录的也是target各字符出现频次的【综合状态】,因此容易想到子问题出现与否只与target中每一位是否能被sticker构造相关(顺序无关),而target长度最大只有15位,因此可以用int数组表示当前位是否被选择,消耗内存O(1 << N).

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云瓣

探寻 webpack 插件机制

webpack 可谓是让人欣喜又让人忧,功能强大但需要一定的学习成本。在探寻 webpack 插件机制前,首先需要了解一件有意思的事情,webpack 插件机制...

2757
来自专栏社区的朋友们

企鹅社区移动版Vue2.0升级手记

引入Vue框架比较早,随着2.0的升级,受到业界的高度关注,应用也越来越广泛,所以我们也得跟上步伐。企鹅社区移动版前端采用VUE 1.0开发。随着官方2.0的推...

2.5K0
来自专栏JackeyGao的博客

Django小技巧12: 禁用单元测试的Migrations

Migrations 无疑是 Django 的一大特色功能,当它在单元测试的时候, 却会加长整个单元测试的时间。特别是你的migrations history特...

713
来自专栏软件开发

前端MVC学习总结(三)——AngularJS服务、路由、内置API、jQueryLite

一、服务 AngularJS功能最基本的组件之一是服务(Service)。服务为你的应用提供基于任务的功能。服务可以被视为重复使用的执行一个或多个相关任务的代码...

1995
来自专栏漫漫前端路

关于一些Vue的文章。(7)

首先安利一波福利,有没有用vscode的小伙伴?推荐一个神奇的字体,自从用了这个字体,敲代码效率简直上天了。先上图看看效果:

905
来自专栏软件开发

前端MVC学习总结(一)——MVC概要与angular概要、模板与数据绑定

一、前端MVC概要 1.1、库与框架的区别 ? 框架是一个软件的半成品,在全局范围内给了大的约束。库是工具,在单点上给我们提供功能。框架是依赖库的。Angula...

24610
来自专栏极乐技术社区

用 RxJS、RxWX 编写微信小程序

RxJS RxJS是微软推出的ReactiveX系列,符合纯函数特点的第三方开源库有非常著名underscore和lodash,以及更加强大的RxJS。它可以用...

3058
来自专栏软件开发

前端MVC学习总结(一)——MVC概要与angular概要、模板与数据绑定

框架是一个软件的半成品,在全局范围内给了大的约束。库是工具,在单点上给我们提供功能。框架是依赖库的。AngularJS是框架而jQuery则是库。

853
来自专栏软件开发

前端MVC Vue2学习总结(二)——Vue的实例、生命周期与Vue脚手架(vue-cli)

一、Vue的实例 1.1、创建一个 Vue 的实例 每个 Vue 应用都是通过 Vue 函数创建一个新的 Vue 实例开始的: var vm = new Vue...

4607
来自专栏前端儿

pushState、replaceState、onpopstate 实现Ajax页面的前进后退刷新

再通过 onhashchange 事件监听hash锚点的变化,手动进行前进后退操作,浏览器支持度

651

扫码关注云+社区