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 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

Java8 Stream 语法详解 & 用法实例《Kotlin极简教程》正式上架:

本文将会详细讲解Stream的使用方法(不会涉及Stream的原理,因为这个系列的文章还是一个快速学习如何使用的)。 1. Stream初体验 我们先来看看...

1162
来自专栏醒者呆

正则表达式——Java程序员懂你

正则表达式 关键字:正则表达式,Pattern,Matcher,字符串方法,split,replace 前文书立下了一个flag,这里要把它完成,就是正则...

3565
来自专栏Java爬坑系列

【Java】单词倒序输出

  如何将一段单词倒序输出?把“Hello Java Hello China”变成“China Hello Java Hello”?   看起来好像很简单,只需...

2378
来自专栏zingpLiu

Python实现计算器

前几天有个面试题目:计算字符串"1 + (5 - 2) * 3",结果为10,不能用eval()。今天介绍一下用压栈的方法解一解这个题目,事实上我们的计算器原理...

1213
来自专栏余林丰

7.哈希

  哈希(Hash)又称散列,它是一个很常见的算法。在Java的HashMap数据结构中主要就利用了哈希。哈希算法包括了哈希函数和哈希表两部分。我们数组的特性可...

2309
来自专栏java一日一条

Java LinkedHashMap工作原理及实现

在理解了#7 介绍的HashMap后,我们来学习LinkedHashMap的工作原理及实现。首先还是类似的,我们写一个简单的LinkedHashMap的程序:

702
来自专栏前端杂货铺

深入instanceof

本文参考摘自这里 规范中 instanceof 运算符定义 11.8.6 The instanceof operator The production...

2868
来自专栏杨熹的专栏

Day 1-Java-imooc-4.流程控制语句

课程地址:http://www.imooc.com/learn/85 总结图片来自 http://www.imooc.com/article/10535 ? 本...

3415
来自专栏于晓飞的专栏

Java 泛型进阶

在 List<String> 中添加 Integer 将不会通过编译,但是List<Sring>与List<Integer>在运行时的确是同一种类型。

1563
来自专栏java一日一条

Java常用排序算法/程序员必须掌握的8大排序算法

1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)

592

扫码关注云+社区