c++ BFS solution with Explanation


  • 0
    B

    Pretty long and hairy, but got AC. Basically for each sticker that can reduce some letter in the target, we use it to reduce the target letter count, and keep the residual's in a set to help remove duplicates (to trim the paths a bit). So for each level of the BFS search, we need to do a double loop, check each residual against each sticker. I was concerned about the residuals set getting too large, but it seemed to work.

    class Solution {
    private:
        int deltacnt(vector<int>& scnt, const vector<int>& tcnt) {
            int cnt=0;
            for (int i=0;i<26;i++) if (scnt[i]&&tcnt[i]) cnt+=min(scnt[i],tcnt[i]);
            return cnt;
        }
        vector<int> deltarm(vector<int>& scnt, const vector<int>& tcnt) {
            vector<int> residual(26,0);
            for (int i=0;i<26;i++) residual[i]=max(0,tcnt[i]-scnt[i]);
            return residual;
        }
        bool residual0(const vector<int>& tcnt) {
            for (int e:tcnt) if (e) return false;
            return true;
        }
    public:
        int minStickers(vector<string>& stickers, string target) {
            vector<int> tcnt(26,0);
            for (char c:target) tcnt[c-'a']++;
            
            vector<vector<int>> scnts;
            for (string s:stickers) {
                vector<int> scnt(26,0);
                for (char c:s) scnt[c-'a']++;
                if (deltacnt(scnt,tcnt)) scnts.push_back(scnt);
            }
            
            set<vector<int>> residuals {tcnt};
            int lvl=0;
            while (!residuals.empty()) {
                set<vector<int>> resnext;
                for (const vector<int>& residual:residuals) {
                    for (vector<int>& scnt:scnts) {
    
                        // check if target is complete
                        if (residual0(residual)) return lvl;
    
                        // add a residual if some letters can be reduced by the sticker
                        if (deltacnt(scnt,residual)) resnext.insert(deltarm(scnt,residual));
                    }
                }
                residuals.swap(resnext);
                lvl++;
            }
            return -1;
        }
    };
    

Log in to reply
 

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