C++ DFS solution


  • 0
    P
    void dfs(int &minRmv, set<string> &st, string &s, int index, int nrmv, int stk, string curstr) {
        // bound
        if (nrmv > minRmv || stk > s.size() - index) return;
        // end case
        if (index == s.size()) {
            if (stk == 0) {
                if (nrmv < minRmv) {
                    minRmv = nrmv;
                    st.clear();
                }
                st.insert(curstr);
            }
            return;
        }
        // not par
        if (s[index] != '(' && s[index] != ')') {
            dfs(minRmv, st, s, index + 1, nrmv, stk, curstr + s[index]);
            return;
        }
        // not remove
        if (s[index] == '(') dfs(minRmv, st, s, index + 1, nrmv, stk + 1, curstr + '(');
        if (s[index] == ')' && stk > 0) dfs(minRmv, st, s, index + 1, nrmv, stk - 1, curstr + ')');
        // remove
        dfs(minRmv, st, s, index + 1, nrmv + 1, stk, curstr);
    }
    
    vector<string> removeInvalidParentheses(string s) {
        int minRmv = INT_MAX;
        set<string> st;
        dfs(minRmv, st, s, 0, 0, 0, "");
        vector<string> ans;
        copy(st.begin(), st.end(), back_inserter(ans));
        return ans;
    }

Log in to reply
 

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