题目描述

leetcode691.贴纸拼词

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 −1 。

注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。

示例 1：

1
2
3
4
5
6
7
8
输入： stickers = ["with","example","science"], target = "thehat"

输出：3

解释：
我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。

示例 2:

1
2
3
4
5
输入：stickers = ["notice","possible"], target = "basicbasic"

输出：-1

解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示:

  • n==stickers.length
  • 1<=n<=50
  • 1<=stickers[i].length<=10
  • 1<=target<=15
  • stickers[i] 和 target 由小写英文单词组成

题解——标准回溯模板+剪枝 12ms

leetcode691.3.png
回溯思路:用一个remains表示剩下的需要寻找的字符串,一个num保存用的贴纸数,每一层查找尝试着用一张贴纸尽可能地找出remains中的字母

同时++num,如果num>=answer,说明不是最小贴纸数,停止搜索;如果remains==””,说明找到了,且num<answer,那么更新answer

关于剪枝:常规思路是每一次都遍历整个stickers,只要这个字符串中有target的字母就尝试搜索,也就是用find_first_of来判断

但实际上,我们可以人为地规定顺序,要求stickers[i]中必须有target[0]才查找,这对结果是无影响的

因为我们一定会需要有第一个字母的贴纸,所以先查找也无妨,但是效率影响是很大的

另外,用一个memo保存之前找到某个remains所用的最小num,如果现在的remains找过了且num>=记录值,终止搜索

(由于target.size()<=15,可知answer<=15||answer==-1,所以先假定answer==16,如果经历搜索仍为16,说明找不到) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int answer=16;//存放答案
    int num=0;//记录已经使用的贴纸数
    unordered_map<string,int> memo;//保存之前找到某个remains所用的最小num
    void solve(vector<string> &stickers,string &remains)
    {
        if(remains=="")//成功贴出,且num<answer(在上一层控制)
            answer=num;
        if(num>=answer-1)//如果num>=answer-1,最终答案不会比answer小,终止搜索
            return ;
        for(int i=0;i<stickers.size();++i)
        {
            if(stickers[i].find(remains[0])!=stickers[i].npos)
            {
                string temp=stickers[i],copy=remains;//拷贝stickers[i]和remains
                int pos=0;
                for(int j=0;j<remains.size();++j)//删除remains中能用temp贴的所有字母
                    if((pos=temp.find(remains[j]))!=temp.npos)
                    {
                        temp.erase(pos,1);
                        remains.erase(j,1);
                        --j;
                    }
                ++num;//贴纸数+1
                auto it=memo.find(remains);//尝试在memo中找remains
                if(it==memo.end()||it->second>num)//找不到remains或者记录值更大,执行替换和搜索
                {
                    memo[remains]=num;
                    solve(stickers,remains);
                }
                remains=copy;//回溯至原状态
                --num;
            }
        }
    }
    int minStickers(vector<string>& stickers, string target) {
        solve(stickers,target);
        return answer==16?-1:answer;//answer==16说明没找到
    }
};