leetcode 691. Stickers to Spell Word 拼接单词 + 深度优先遍历DFS

以你之姓@ 2022-06-03 09:28 157阅读 0赞

We are given N different types of stickers. Each sticker has a lowercase English word on it.

You would like to spell out the given target string by cutting individual letters from your collection of stickers and rearranging them.

You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

What is the minimum number of stickers that you need to spell out the target? If the task is impossible, return -1.

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.

还没搞懂为什么这么做

这道题感觉挺难得，不过看了下答案，豁然开朗，

首先统计所有sticker的字符出现的频率，然后开始递归

使用map做中间结果的保存，然后挨个一次做统计即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int minStickers(vector<string>& stickers, string target) 
        {
            //把所有的字符按照数组存进去
            vector<vector<int>> all(stickers.size(), vector<int>(26, 0));
            for (int i = 0; i < stickers.size(); i++)
            {
                for (char c : stickers[i])
                {
                    all[i][c - 'a']++;
                }
            }
    
            //中间结果的保存查询
            map<string, int> dp;
            dp[""] = 0;
            return dfs(all, dp, target);
        }
    
        int dfs(vector<vector<int>>& all, map<string, int>& dp, string target)
        {
            if (dp.find(target) != dp.end())
                return dp[target];
            else
            {
                //统计目标字符串
                vector<int> tar(26, 0);
                for (char c : target)
                    tar[c - 'a']++;
    
                //针对每一个字典中的字符串依次做处理
                int minStep = INT_MAX;
                for (int i = 0; i < all.size(); i++)
                {
                    //优化，加速计算
                    if (all[i][target[0] - 'a'] == 0)
                        continue;
                    string res;
                    for (int j = 0; j < 26; j++)
                    {
                        if (tar[j] >= all[i][j])
                            res += string(tar[j] - all[i][j], 'a' + j);
                    }
                    int tmp = dfs(all, dp, res);
                    if (tmp != -1)
                        minStep = min(minStep, 1 + tmp);
                }
                //结果回填
                dp[target] = (minStep == INT_MAX) ? -1 : minStep;
                return dp[target];
            }
        }
    };