C++_AC_DFS


  • 0
    class Solution {
    public:
    unordered_map<char, int> mp;
    string update(string s){
        bool same = true;
       // to check whether there is some updates in our string s.
        while(s.size() >= 3 && same){
            for(int i = 0; i + 2 < s.size(); ++i){
                if(i + 2 < s.size() && s[i] == s[i+1] && s[i] == s[i+2]){
                    int len = 3;
                    while(i + len < s.size() && s[i] == s[i + len]) ++len;
                    s.erase(s.begin() + i, s.begin()+i+len);
                    same = true;//Updated
                    break;
                    //because we have updated our string, we need break and re-check our new string
                }else{
                    same = false;
                }
            }
        }
        return s;
    }
    void dfs(string s, int balls, int count, int& res){
        if(s.size() >= 3){s = update(s);}
        if(s.empty()) {res = min(res, count); return;}
        if(balls <= 0){return;}
        //if balls <= 0, which means that this search is not what we want , just stop it.
        for(int i = 0; i < s.size(); ++i){
            if(i + 1 < s.size() && s[i] == s[i+1] && mp[s[i]]){
                char tmp = s[i];
                mp[tmp]--;
                s.insert(s.begin() + i, tmp);
                dfs(s, balls - 1, count + 1, res);
                s.erase(s.begin() + i);
                mp[tmp]++;
            }else if(mp[s[i]] >= 2){
                    char tmp = s[i];
                    mp[tmp] = mp[tmp] - 2;
                    //insert two chars is equal to delete one char.
                    s.erase(s.begin() + i);
                    dfs(s, balls - 2, count + 2, res);
                    s.insert(s.begin() + i, tmp);
                    mp[tmp] = mp[tmp] + 2;
            }
        }
    }
    int findMinStep(string board, string hand) {
        for(auto s : hand){mp[s]++;}
        int res = INT_MAX;
        dfs(board, hand.size(), 0, res);
        return res == INT_MAX ? -1:res;
    }
    };

Log in to reply
 

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