My 0ms C++ solution without recursion and DFS


  • 5
    Z
    class Solution {
        //这一版不使用递归,速度更快。
        //首先是最厚的括号包裹状态,即一开始左边是连续的左括号,右边是连续的右括号,然后执行以下逻辑:
        //1、右括号不能比左括号多;
        //2、弹出右括号,直到遇到第一个左括号,如果左括号改成右括号仍然合法,则把它改成右括号;否则,左括号继续弹出;
        //3、改完之后一个劲加左括号,直到所有可以用的左括号都加完为止。
        //4、循环一直执行到一开始的连续左括号没有为止。
        //该程序是上一版递归程序的等价版。
    public:
        vector<string> generateParenthesis(int n) 
        {
            vector<string> result;
            if(n==0)
                return result;
            string s;
            for(int i=0;i<n;i++)
                s+="(";
            for(int i=0;i<n;i++)
                s+=")";
            int left=n;
            int right=n;
            do
            {
                result.push_back(s);
                while(s!=""&&(s.back()==')'||left-1<right+1))
                {
                    if(s.back()==')')
                        right--;
                    else
                        left--;
                    s.pop_back();
                }
                if(s!="")
                {
                    s.back()=')';
                    left--;
                    right++;
                    while(left<n)
                    {
                        s+="(";
                        left++;
                    }
                    while(right<n)
                    {
                        s+=")";
                        right++;
                    }
                }
            }while(s!="");
            return result;
        }
    };

  • 0
    R

    thnks for the solution


  • 0
    R

    can u explain this solution ? how did u come up with this ?


  • 0
    Z

    In this problem there are 2 kinds of limited cases:
    First we call it the thickest status. For example, assume n=3 then ((())) is the thickest case. You may imagine a layer of bracket as your clothes. In this case you wear 3 shirts, for instance.
    Second we call it the thinnest status. For example assume n=3 then ()()() is the thinnest case, in which you put all your 3 shirts one after another.
    The loop generates status from thickest to thinnest based on several rules:

    1. In any status the right bracket ")" cannot be more than the left bracket "(" once you count the number of brackets from left to right in any position, or the status is invalid.
      For example, ((())) is valid because in any postion of the string ((())), ) is no more than ( if you count from left to right. However ()())(() is not valid because if you stop counting in the third ) you will find you have counted 2 ( and 3 ) which is not valid.

    2.The algorithm starts from the thickest status and pop back the right bracket until it meets the first bracket. If one can alter the "(" with ")" and still keeps the status as valid, then do it. After change one "(" into ")" then we just keep adding the left bracket "(" until it is exhausted, then we begin to add the right bracket ")" until it is exhausted.

    1. The loop never stops until all we reach the first "(".

    For example, we assume n=3 and then simulate the course:

    The first status is the thickest one.
    ((()))
    Then in the first loop, we first pop back the 3 ) and make the string as (((.
    We find the first ( from right and then replace it with ), now the string is (().
    Then we add left brackets, yet we have only one chance because the left bracket is no more than 3. After that the string is (()(.
    Then we add the right brackets, we have 2 chances. In the end the string is (()()).
    One loop is over.

    In the next loop, the status is changed like:
    (()())->(()(->(())->(())(->(())().

    In the next loop, the status is changed like:
    (())()->(())(->(())), but this is not valid, we ignore it and continue to pop back. So the correct routine is:
    (())()->(())(->((->()->()((->()(()).

    In the next loop:
    ()(())->()()->()()().

    In the next loop:
    ()()()->()()(->()())[NOT VALID]->()(->())[NOT VALID]->(.
    We meet the first bracket. The algorithm is over.

    We get all the status is:
    ((())) (()()) (())() ()(()) ()()().
    This confirms with the example shown in the problem. In fact I think this is the essence of the problem.

    Any questions, please reply to my email box: zcj5918@163.com.

    Wishes,

    Zhong


  • 0
    M

    same way, more clean code

    class Solution {
    public:
        std::vector<std::string> generateParenthesis(int n) {
            std::vector<std::string> vec;
            int l = n;
            int r = n;
            std::string stack(n, '(');
            stack.append(n, ')');
            vec.push_back(stack);
            while (stack.length()) {
                char c = stack.back();
                stack.pop_back();
                //backtrace from tail to find a '(' which can be modified to ')'
                if (c == ')') {
                    r--;
                    continue;
                }
                //c == '('
                if (--l > r) {
                    stack.push_back(')'); r++;
                    stack.append(n - l, '(');
                    stack.append(n - r, ')');
                    vec.push_back(stack);
                    l = n; r = n;
                }
            }
            return vec;
        }
    };
    
    

Log in to reply
 

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