贴纸拼词问题
作者：Grey
原文地址:
题目描述
有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。以多次使用每个贴纸，每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。
注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。
题目链接：LeetCode 691. Stickers to Spell Word
暴力解法
定义递归函数
int process(String[] stickers, String target)
递归含义表示：stickers 作为贴纸数组，可以拼凑出 target 字符串的最小贴纸数量是多少。，如果无论如何都无法拼凑出 target，则返回无穷大，即：Integer.MAX_VALUE
接下来是 base case，如果 target 为空串，直接返回 0，表示无须任何贴纸就可以组成，即
if (target.length() == 0) {
// 目标是空串，只需要0张贴纸
return 0;
}
接下来是普遍情况，枚举 stickers 中每一个字符串 s，将 s 中包含的所有字符从 target 移除掉，然后看 target 剩下哪些字符，继续被 stickers 中的字符分解。
定义一个工具函数
String minus(String first, String target)
这个函数实现的功能就是：将 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();
}
暴力解法完整代码如下
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();
}
}
超时
上述暴力过程，可以做一些优化，比如
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']++;
}
}
其中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);
}
}
}
其中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();
}
}
超时
使用动态规划中的缓存法 （可 AC）
在暴力递归中，增加一个参数 Map<String, Integer> map, 其中 key 是 target 字符串，value 是组成这个 target 字符串要耗费的最少贴纸数量，在递归函数中，增加如下逻辑
if (map.containsKey(target)) {
return map.get(target);
}
if (target.length() == 0) {
map.put(target, 0);
return 0;
}
遍历 stickers 得到最少字符串的时候，把结果加入这个哈希表，
map.put(target, ways);
即可。
完整代码如下
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;
}
}