Easy Understand C++ solution using recursion [AC]


  • 0
    S

    The approach is simple. We will first find the number of left and right brackets to remove.

    This can be done using a simple counter approach, where you will increment the left bracket counter on seeing '(' and decrement on seeing ')'. If the value goes negative that means there is an imbalance there and we need to remove a right bracket. So we will increment the right bracket counter.

    We will generate all possible brackets where we can remove 'left' and 'right' number of respective brackets. We will also maintain a counter to check the balance of the brackets as well. If anytime, we reach a negative balance, we will stop the recursion there.

    If we traversed the whole string 's', where we have removed 'left' number of left brackets, 'right' number of right brackets and the bracket balance is 0, we will append it to the result.

    class Solution {
        set<string> res;
        void helper(string s, int i, int left, int right,string temp, int valid)
        {
            if(i == s.length())
            {
                if(valid==0 && left == 0  && right == 0)
                    res.insert(temp);
                return;
            }
            if(valid<0)
                return;
            
            if(s[i]=='(')
            {
                if(left>0)
                    helper(s, i+1, left-1, right, temp, valid);
                
                helper(s, i+1, left, right, temp+"(", valid+1);
            }
            else if(s[i]==')')
            {
                if(right>0)
                    helper(s, i+1, left, right-1, temp, valid);
                helper(s, i+1, left, right, temp+")", valid-1);
            }
            else
                helper(s, i+1, left, right, temp+s[i], valid);
        }
    public:
        vector<string> removeInvalidParentheses(string s) {
            int left  = 0;
            int right = 0;
            for(int i = 0;i<s.length();i++)
            {
                if(s[i]=='(')
                {
                    left++;
                }
                else if(s[i]==')')
                {
                    if(left>0)
                        left--;
                    else
                        right++;
                }
            }
            
            helper(s, 0, left, right, "", 0);
            vector<string>  out(res.begin(),res.end());
            return out;
        }
    };
    

Log in to reply
 

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