lintcode 1081 · 贴纸拼单词【hard 递归+记忆化搜索才能通过】

题目

https://www.lintcode.com/problem/1081/

给出N种不同类型的贴纸。 每个贴纸上都写有一个小写英文单词。
通过裁剪贴纸上的所有字母并重排序来拼出字符串target。
每种贴纸可以使用多次，假定每种贴纸数量无限。
拼出target最少需要多少张贴纸？如果不可能拼成，则返回-1。stickers的长度范围为[1, 50].
stickers仅由小写英文字母组成(没有撇号').
target的长度范围为[1, 15]，而且由小写字母组成。
在所有的测试用例中，单词是从1000个最常见的美国英文单词中任意选择的，目标单词则是由两个任意单词拼接而成。
时间限制可能比以往更有挑战性，期望的时间界是平均35毫秒50个测试样例。
样例
样例 1:输入：
["with", "example", "science"], "thehat"
输出：
3
解释：
使用两张"with"和一张"example"，经过裁剪和重排字母，可以得到"thehat"。这也是所需要的最少贴纸数。
样例 2:输入：
["notice", "possible"], "basicbasic"
输出：
-1
解释：
无法拼成"basicbasic"。

思路

注意：单纯使用递归无法通过，需要使用递归+词频统计优化【贪心思想】+记忆化搜索才能通过
思路：每一次尝试，目标单词第一个字符在当前字符中，就以当前字符为第一个字符，去递归

参考代码

public class Solution {/*** @param stickers: a string array* @param target: a string* @return: the minimum number of stickers that you need to spell out the target*/public int minStickers(String[] stickers, String target) {//int ans = f1(stickers, target);  //直接递归，会超时//int ans = f2(stickers, target);  //优化了，使用词频表统计，还是会超时int ans = f3(stickers, target);  //优化了，使用词频表统计，加上记忆化搜索return ans == Integer.MAX_VALUE ? -1 : ans;}public static int f1(String[] stickers, String target) {if (target.length() == 0)return 0;int min = Integer.MAX_VALUE;for (String first : stickers) {String rest = minus(target, first);if (rest.length() != target.length()) {min = Math.min(min, f1(stickers, rest));}}return min + (min == Integer.MAX_VALUE ? 0 : 1);}public static String minus(String s1, String s2) {char[] str1 = s1.toCharArray();char[] str2 = s2.toCharArray();int[] cnt = new int[26];for (char c : str1) {cnt[c - 'a']++;}for (char c : str2) {cnt[c - 'a']--;}StringBuilder sb = new StringBuilder();for (int i = 0; i < 26; i++) {if (cnt[i] > 0) {for (int j = 0; j < cnt[i]; j++) {sb.append((char) (i + 'a'));}}}return sb.toString();}public static int f2(String[] stickers, String target) {int n = stickers.length;//关键优化，词频统计表int[][] cnt = new int[n][26];for (int i = 0; i < n; i++) {char[] str = stickers[i].toCharArray();for (char c : str) {cnt[i][c - 'a']++;}}int ans = process(cnt, target);return ans == Integer.MAX_VALUE ? -1 : ans;}//stickers[i] 数组，当初i号贴纸的字符统计，int[][] stickers ->所有贴纸//每一种贴纸都有无穷张//返回搞定target的最少张树//最少张数public static int process(int[][] stickers, String t) {if (t.length() == 0) return 0;char[] target = t.toCharArray();int[] tcnt = new int[26];for (char c : target) {tcnt[c - 'a']++;}int n = stickers.length;int min = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {//尝试每一张贴纸是谁int[] sticker = stickers[i];//最关键优化（剪枝，这一步也是贪心）if (sticker[target[0] - 'a'] > 0) {StringBuilder sb = new StringBuilder();for (int j = 0; j < 26; j++) {if (tcnt[j] > 0) {int nums = tcnt[j] - sticker[j];for (int k = 0; k < nums; k++) {sb.append((char) (j + 'a'));}}}String rest = sb.toString();min = Math.min(min, process(stickers, rest));}}return min + (min == Integer.MAX_VALUE ? 0 : 1);}public static int f3(String[] stickers, String target) {int n = stickers.length;int[][] cnts = new int[n][26];for (int i = 0; i < n; i++) {char[] str = stickers[i].toCharArray();for (char c : str) {cnts[i][c - 'a']++;}}Map<String, Integer> dp = new HashMap<>();dp.put("", 0);int ans = process3(cnts, target, dp);return ans == Integer.MAX_VALUE ? -1 : ans;}public static int process3(int[][] stickers,String t ,Map<String,Integer> dp){if(dp.containsKey(t))return dp.get(t);char[] target = t.toCharArray();int[] tcnt = new int[26];for (char c : target) {tcnt[c-'a']++;}int n = stickers.length;int min = Integer.MAX_VALUE;for (int i = 0; i <n ; i++) {int[] sticker = stickers[i];if(sticker[target[0]-'a'] >0){StringBuilder sb = new StringBuilder();for (int j = 0; j <26 ; j++) {if(tcnt[j] >0){int nums = tcnt[j]-sticker[j];for (int k = 0; k <nums ; k++) {sb.append((char)(j+'a'));}}}String rest = sb.toString();min = Math.min(min,process3(stickers,rest,dp));}}int ans = min+(min ==Integer.MAX_VALUE?0:1);dp.put(t,ans);return ans;}
}