# LWC 53：691. Stickers to Spell Word

## LWC 53：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.

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

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

98 篇文章33 人订阅

0 条评论

## 相关文章

### 探寻 webpack 插件机制

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

2757

2.5K0

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

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

713

1995

905

24610

### 用 RxJS、RxWX 编写微信小程序

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

3058

853

4607

651