# 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 条评论

## 相关文章

1162

3565

### 【Java】单词倒序输出

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

2378

1213

### 7.哈希

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

2309

702

2868

3415

1563

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

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

592