Easy to understand C++ with explanation


  • 0

    Summary: continually apply stickers to the target string, attempting to reduce the target string to an empty string through iterative backtracking and recursion with constraint. Keep track of the ongoing minimum amount of stickers needed to construct each reduced target string. ( i.e. +1 to the ongoing count minCnt for each sticker which meets the recursive constraint when propagating back up the recursive stack. ) The recursive constraint is NOT met when iterative backtracking results in a target string which CANNOT be further reduced ( see Base case 2 below for more details ).

    Target reduction formula:
    next target = current target MINUS current sticker

    Use a hash table to keep track of the minimum count of stickers needed to construct the target string. The key of this hash table is the target string ( along with the various reduced target strings constructed by applying a sticker to the target ). Applying a sticker to a target is the act of removing from the target the common amount of chars between the target and sticker. The value of this hash table is the ongoing minimum count of stickers needed to create the target string.

    Use iterative backtracking to apply each sticker multiple times and in different orders to try and find new minimums for each new target created by applying each sticker to the current target.

    Use recursion following constraint which is satisfied if and only if the current sticker applied has reduced the target size. The base case occurs in two different ways, depending on the input.

    Base case 1: If the set of chars included in the target are a subset of the set of chars from the stickers ( i.e. the stickers can be used in some repetition/combination to completely construct the target ), then the target string will be reduced to an empty string through recursion, and the hash lookup of an empty string returns 0. This means that there are 0 stickers used to create the empty target string "". The hash table is initialized with this entry.

    Base case 2: If the set of chars included in the target are NOT a subset of the set of chars from the stickers ( i.e. the stickers CANNOT be used to construct the target ), then the recursive constraint will NOT be passed at some point, and the target will NEVER be an empty string. In this case, once iterative backtracking completes, one of the recursive calls will return -1 since the target string CANNOT be further reduced at some point. The return value -1 is propagated back up the recursive stack and overwrites any and all positive minimum counts calculated so far ( minCnt ), since -1 is the min() of itself compared to any positive integer tracked by minCnt.

    Solution: both base case 1 and base case 2 are used to propagate -1 or minCnt back up the recursive stack though the hash table once iterative backtracking and constrained recursion complete.

    class Solution {
    private:
        vector<int> to_vector(const string &s){
            vector<int> res(26, 0);
            for (auto&& ch : s) ++res[ch-'a']; // one vector index per char [a:z]
            return res;
        }
        
        string applySticker(const vector<int>& sticker, const vector<int>& target){
            string res{};
            for (int i=0; i < target.size(); ++i){ // for each char position
                if (target[i] && sticker[i]){
                    int leftovers=target[i]-sticker[i];
                    if (leftovers > 0) res+=string(leftovers,i+'a'); // apply char, keep leftovers
                }
                else if (target[i]) res+=string(target[i],i+'a'); // char NOT applied
            }
            return res; // alphabetically sorted target MINUS common chars from applying sticker
        }
        
        int getMinStickersToCreateTarget(const vector<string>& stickers,
            const string& target, unordered_map<string,int>& hash){
            if (hash.count(target)) return hash[target]; // base case 1
            int minCnt=INT_MAX;
            vector<int> vt=to_vector(target);
            for (int i=0; i<stickers.size(); ++i){ // iterative backtracking
                vector<int> vs=to_vector(stickers[i]);
                string next_target=applySticker(vs,vt);
                if (next_target.size() < target.size()){ // recursive constraint
                    int currCnt=getMinStickersToCreateTarget(stickers,next_target,hash);
                    if (currCnt!=-1) minCnt=min(minCnt,currCnt+1); // +1 sticker applied
                }
            }
            return hash[target]=minCnt==INT_MAX ? -1 : minCnt; // base case 2
        }
        
    public:
        int minStickers(vector<string>& stickers, string target) {
            unordered_map<string,int> hash({{"",0}});
            return getMinStickersToCreateTarget(stickers,target,hash);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.