題目
給定一個字串str，給定一一個字串型別的陣列arr，
arr里的每一個字串，代表一張貼紙，你可以把單個字符剪開使用，目的是拼出str來，
回傳需要至少多少張貼紙可以完成這個任務，
例子: str= “babac”，arr = {“ba”,“c”,“abcd”}
至少需要兩張貼紙"ba"和"abcd"，因為使用這兩張貼紙，把每一個字符單獨剪開，含有2個a、2個b、1個c，是可以拼出str的，所以回傳2，
提示：可變引數能少則少，可變引數越少，快取結構的命中率越高
package com.harrison.class13;
import java.util.HashMap;
public class Code07_StickersToSpellWord {
// 偽代碼
// public static int getMinStickers(String rest,String[] arr) {
// // 加過濾 保證所有貼紙里的字符能夠覆寫目標字串
// }
//
// public static int minStickers(String rest,String[] arr) {
// if(rest.equals("")) {
// return 0;
// }
// int next=0;
// for(String first:arr) {
// rest-first -> nextRest;
// int cur=minStickers(nextRest, arr);
// next=Math.min(next, cur);
// }
// return next+1;
// }
public static int minStickers1(String[] stickers,String target) {
int n=stickers.length;
int[][] map=new int[n][26];
for(int i=0; i<n; i++) {
char[] str=stickers[i].toCharArray();
for(char c:str) {
map[i][c-'a']++;
}
}
HashMap<String, Integer> dp=new HashMap<>();
dp.put("", 0);
return process1(dp, map, target);
}
// dp 傻快取，如果rest已經算過了，直接回傳dp中的值
// 0...N中每一個字串所含字符的詞頻統計
// 回傳值是-1，map中的貼紙無論如何都無法搞定rest
public static int process1(HashMap<String, Integer> dp,int[][] map,String rest) {
if(dp.containsKey(rest)) {
return dp.get(rest);
}
// 搞定rest，使用最少的貼紙數量
int ans=Integer.MAX_VALUE;
// n種貼紙
int n=map.length;
// tmap替代rest
int[] tmap=new int[26];
char[] target=rest.toCharArray();
for(char c:target) {
tmap[c-'a']++;
}
// map-tmap
for(int i=0; i<n; i++) {// 列舉當前第一張貼紙是誰
// 小貪心 確保貼紙中至少含有目標字串中的一種字符才進行嘗試
// 目標字串中0位置的字符，當前貼紙是否有
if(map[i][target[0]-'a']==0) {
continue;
}
StringBuilder sb=new StringBuilder();
// i 當前來到的第一張貼紙
// j 列舉a~z字符
for(int j=0; j<26; j++) {
if(tmap[j]>0) {// j這個字符是target需要的（要搞定的字串里有這個字符）
for(int k=0; k<Math.max(0, tmap[j]-map[i][j]); k++) {
sb.append((char)('a'+j));
}
}
}
// 經歷上面的for回圈后，目標字串減去了第一張貼紙(i)里的字符，
// 剩余的字符在sb里面
String s=sb.toString();
int tmp=process1(dp, map, s);
if(tmp!=-1) {
ans=Math.min(ans, tmp+1);
}
}
dp.put(rest, ans==Integer.MAX_VALUE?-1:ans);
return dp.get(rest);
}
public static void main(String[] args) {
String[] arr= {"aaaa","bbaa","ccddd"};
String str="abcccccdddddbbbaaaaa";
System.out.println(minStickers1(arr,str));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/413956.html
標籤：其他
上一篇：青蛙跳臺階問題（和進階）