0ms c++ iterative, not DP solution. using only vectors, with explanation


  • 0
    D

    logic here is simple:

    First, store a result vector, then for every entry:

    • add '(', when cannot add ')'

    • add ')', when cannot add '('

    • copy this entry and add '(' and ')' separately to original and new copy, when both are valid

    here count and countleft are vectors that store check values.

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            vector<string> result(1);
            vector<int> count(1,0),countleft(1,0);
            for(int i=0;i<2*n;++i){
                int m=count.size();
                for(int j=0;j<m;++j){
                    if(count[j]==0){
                        result[j]+='(';
                        count[j]++;
                        countleft[j]++;
                    }
                    else if(countleft[j]==n) result[j]+=')';
                    else{
                        result.push_back(result[j]+')');
                        count.push_back(count[j]-1);
                        countleft.push_back(countleft[j]);
                        result[j]+='(';
                        count[j]++;
                        countleft[j]++;
                    }
                }
            }
            return result;
        }
    };

Log in to reply
 

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