Iterative solution, clear & concise


  • 0
    X

    Iterative solution, using manual logic to simulate the recursive call stack. What you guys think.

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> result;
            string cur;
            bool pushed;
            int left = 0, right = 0;
            char popped;
            
            cur.push_back('(');
            left++;
            pushed = true;
            
            
            while(cur.length() > 0){
                
                if(left==n && left==right) result.push_back(cur);
                
                if(pushed){
                    if(left<n){
                        push_helper(cur, left, right, '(');
                        pushed = true;
                    }
                    else if(left>right){
                        push_helper(cur, left, right, ')');
                        pushed = true;
                    }
                    else{
                        pop_helper(cur, left, right, popped);
                        pushed = false;
                    }
                }
                
                
                else{
                    if(popped==')'){                                    
                        pop_helper(cur, left, right, popped);
                        pushed = false;
                    }
                    else if(popped=='('){
                        if(left>right){
                            push_helper(cur, left, right, ')');
                            pushed = true;
                        }else{
                            pop_helper(cur, left, right, popped);
                            pushed = false;
                        }
                    }
                }//end if-else
            }//end while
            
            return result;
        }
        
        void pop_helper(string& cur, int& left, int& right, char& popped){
            popped = cur.back();
            cur.pop_back();
            if(popped == '(') left--;
            else right--;
        }
        void push_helper(string& cur, int& left, int& right, char toPush){
            cur.push_back(toPush);
            if(toPush == '(') left++;
            else right++;
        }
    };
    

Log in to reply
 

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