# c++ BFS solution with Explanation

• 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;
}
};
``````

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