488. Zuma Game

https://leetcode.com/problems/zuma-game/

Solution:
will use dsf strategy to find the minimum steps for reaching the end(empty string). If find two same adjacent elements and also have more than one at hand, then match to cancel them; if can only find one element which is different from its left and right neighbors, and there are more than two that kind of elements at hand, then add two to match to cancel. After each canceling, need to consider possible sequential canceling. For example, GGRRGG. When the mid RR was cancelled, then the rest GGGG will cancel automatically.

Code:

class Solution {
public:
    int findMinStep(string board, string hand) {
        int res = INT_MAX;
        vector<int> v(26, 0);
        for(auto a:hand) ++v[a-'A'];
        dsf(board, hand.size(), v, 0, res);
        return res==INT_MAX?-1:res;
    }
private:
    void dsf(string b, int l, vector<int> &v, int count, int &r){
        if(b.size()>=3) b = helper(b);
        if(b.empty()) r = min(r, count);
        else if(l<=0) return;
        else{
            for(int i=0; i<b.size(); ++i){
                if(i<b.size()-1 && b[i]==b[i+1] && v[b[i]-'A']){
                    --v[b[i]-'A'];
                    b.insert(i+b.begin(), b[i]);
                    dsf(b, l-1, v, count+1, r);
                    b.erase(i+b.begin());
                    ++v[b[i]-'A'];
                }
                else{
                    if(v[b[i]-'A'] >= 2){
                        v[b[i]-'A'] -= 2;
                        char t = b[i];
                        b.erase(i+b.begin());//corner case: b may become empty now.
                        dsf(b, l-2, v, count+2, r);
                        b.insert(i+b.begin(), t);
                        v[b[i]-'A'] += 2;
                    }
                }
            }
        }
    }
    string helper(string s){
        bool flag = true;
        while(s.size()>=3 && flag){
            for(int i=0; i<s.size()-2; ++i){
                if(s[i]==s[i+1] && s[i] == s[i+2]){
                    int t = 3;
                    while(i+t<s.size() && s[i] == s[i+t]) ++t;//more than 3. 
                    s.erase(s.begin()+i, s.begin()+i+t);
                    flag = true;
                    break;
                }
                else flag = false;
            }
        }
        return s;
    }
};