中山优化网站,重庆交通建设集团有限公司网站,app定制开发网站有哪些,ios wordpress题目
https://www.lintcode.com/problem/1081/
给出N种不同类型的贴纸。 每个贴纸上都写有一个小写英文单词。
通过裁剪贴纸上的所有字母并重排序来拼出字符串target。
每种贴纸可以使用多次#xff0c;假定每种贴纸数量无限。
拼出target最少需要多少张贴纸#xff1f;如果…题目
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];}}MapString, 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 ,MapString,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)(ja));}}}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;}
}
