问题:
给定一堆单词卡,每个单词可以有无限张同样的卡片。
要从这些单词卡中选择一些,进行剪切拼接,要构成目标单词,求需要的最少卡片数量。
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.
解法:DFS(深度优先搜索)
- 当前状态:
- 当前目标串target,所需要的最少卡片数。
- 选择:
- 在所有单词卡中选择,选择后,剩下的字符再进行递归匹配,得到最少卡片数+1,为当前选择的结果。
- 在这些结果的有效结果(剩下字符递归结果!=-1)中,求res=最小值min
- 将最小值最为本次递归的结果返回 return res,同时保存在结果map:dp中:dp[target]=res。
- 退出递归条件:
- dp中保存过,当前目标串target的结果,直接返回dp[target]
- 当前target串="",则返回0。(或者提前保存dp[""]=0)
♻️ 优化:
Optimization: If the target can be spelled out by a group of stickers, at least one of them has to contain character target[0]. So I explicitly require next sticker containing target[0], which significantly reduced the search space.
// 这个优化剪枝很神奇,可以避免潜在的对target完全没有贡献的sticker,暂时无法贡献的sticker等到其他sticker把部分target拼凑出来以后再贡献
代码参考:
1 class Solution { 2 public: 3 //dp[s]: for string s, the min number of stickers need. 4 unordered_map<string, int> dp; 5 int dfs(vector<vector<int>>mp, string target) { 6 //return already gotten result. 7 if(dp.count(target)) return dp[target]; 8 //if not already got, then following process: 9 int res = INT_MAX; 10 //get alphbet map of this target string. 11 vector<int>tgmp(26,0); 12 for(char a:target) { 13 tgmp[a-'a']++; 14 } 15 //opt: check every sticker 16 for(int j=0; j<mp.size(); j++) { 17 //every alphbet of this sticker 18 //optimization: 19 //If the target can be spelled out by a group of stickers, 20 //at least one of them has to contain character target[0]. 21 //So I explicitly require next sticker containing target[0], 22 //which significantly reduced the search space. 23 if(mp[j][target[0]-'a']==0)continue; 24 //process 25 string nexttarget; 26 for(int i=0; i<26; i++) { 27 if(tgmp[i]>mp[j][i]) { 28 int leftAlphbetCount = tgmp[i]-mp[j][i]; 29 nexttarget += string(leftAlphbetCount, 'a'+i); 30 } 31 } 32 // if (nexttarget == target) continue; 33 // 如果没有之前那个优化,一定要判断新target和原target是否一样,避免重复递归 34 int tmp = dfs(mp, nexttarget); 35 if(tmp!=-1) res = min(res, tmp+1); 36 } 37 dp[target] = (res==INT_MAX?-1:res); 38 return dp[target]; 39 } 40 int minStickers(vector<string>& stickers, string target) { 41 //get alphbet map of every word 42 int sn = stickers.size(); 43 vector<vector<int>>mp(sn, vector<int>(26, 0)); 44 for(int i=0; i<sn; i++) { 45 for(char a:stickers[i]) { 46 mp[i][a-'a']++; 47 } 48 } 49 dp[""]=0; 50 return dfs(mp, target); 51 } 52 };