An iterative method.


  • 159
    L

    My method is DP. First consider how to get the result f(n) from previous result f(0)...f(n-1).
    Actually, the result f(n) will be put an extra () pair to f(n-1). Let the "(" always at the first position, to produce a valid result, we can only put ")" in a way that there will be i pairs () inside the extra () and n - 1 - i pairs () outside the extra pair.

    Let us consider an example to get clear view:

    f(0): ""

    f(1): "("f(0)")"

    f(2): "("f(0)")"f(1), "("f(1)")"

    f(3): "("f(0)")"f(2), "("f(1)")"f(1), "("f(2)")"

    So f(n) = "("f(0)")"f(n-1) , "("f(1)")"f(n-2) "("f(2)")"f(n-3) ... "("f(i)")"f(n-1-i) ... "(f(n-1)")"

    Below is my code:

    public class Solution
    {
        public List<String> generateParenthesis(int n)
        {
            List<List<String>> lists = new ArrayList<>();
            lists.add(Collections.singletonList(""));
            
            for (int i = 1; i <= n; ++i)
            {
                final List<String> list = new ArrayList<>();
                
                for (int j = 0; j < i; ++j)
                {
                    for (final String first : lists.get(j))
                    {
                        for (final String second : lists.get(i - 1 - j))
                        {
                            list.add("(" + first + ")" + second);
                        }
                    }
                }
                
                lists.add(list);
            }
            
            return lists.get(lists.size() - 1);
        }
    }

  • 0
    W

    Nice! thanks.


  • 0
    J

    Nice!!!!!!!!


  • -2
    K

    Thanks a lot ! Your solution is perfect!!!


  • 0
    W

    very good solution!


  • 0
    J

    pretty awesome


  • 0
    J

    I don't get this :/
    How do you know/prove this is correct?


  • 0
    S
    This post is deleted!

  • 20
    W

    I think it's useful to prove this equation.

    The equation is equivalent to the following one:

    f(n) = (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0)

    First, let f(n) to be a correct solution set when there is n pair of parentheses.
    This means every combination in f(n) is a valid combination, and any combination which isn't in f(n) is not a valid combination for n.
    And we can easily get the first three solution sets i.e. f(0) = {""}, f(1) = {"()"} f(2) = {"()()", "(())"}.

    For any n > 2, each combination of f(n) can be divided into two parts p0 and p1.
    p0 and p1 has several properties:

    1. Parentheses in both p0 and p1 can match wel
    2. p0 should be as short as possible but not empty. This means that p0 belongs to (f(l0-1)) where l0 is the number of pairs in p0.
      This property can be proved easily. Shortest means the first left parenthesis in this combination always matches the last right parenthesis.
      So without these two, what left is also a legal combination.

    Now, let's reorganize f(n) by p0.
    Put those combinations with same length of p0 into a same set, and then f(n) is divided into several subsets.
    Each combination in subset s whose p0 has l0 pair of parentheses also belongs to the set (f(l0-1))f(n-l0).
    So we can get f(n) belongs to (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0).

    OK, the only thing to prove now is (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0) also belongs to f(n).
    Notice that each combination in (f(i))f(n-1-i) is a legal combination for n, and we've declared before that each legal combination for n belongs to f(n).
    So each combination in the left side of equation belongs to f(n), and the left side as a whole set belongs to f(n).

    Prove complete.


  • 0
    C

    what is the time complexity for this one? O(n^4)?


  • 1
    M

    Another iterative method with complexity O(n^2)

        LinkedList<String> queueBracket = new LinkedList<>();
        queueBracket.add("(");
    
        // 0 means # of left brackets; 1 means # of right brackets
        LinkedList<List<Integer>> queueBracketNum = new LinkedList<>();
        queueBracketNum.add(Arrays.asList(new Integer[]{1, 0}));
    
        for (int i = 1; i <= n * 2 - 1; i++) {
            while (queueBracket.peek().length() == i) {
                String bracket = queueBracket.remove();
                List<Integer> bracketNum = queueBracketNum.remove();
    
                if (bracketNum.get(0) < n) {
                    queueBracket.add(bracket + "(");
                    queueBracketNum.add(Arrays.asList(new Integer[]{bracketNum.get(0) + 1, bracketNum.get(1)}));
                }
    
                if (bracketNum.get(0) > bracketNum.get(1) && bracketNum.get(1) < n) {
                    queueBracket.add(bracket + ")");
                    queueBracketNum.add(Arrays.asList(new Integer[]{bracketNum.get(0), bracketNum.get(1) + 1}));
                }
            }
        }
    
        return queueBracket;

  • 0
    D

    Thanks for the explanations!


  • 4
    W

    Too many loops and containers. How about this:

    vector<string> generateParenthesis(int n) {
        vector<string> result;
        if (!n) return result;
        
        string s(n, '(');
        s.append(n, ')');
        
        for (;;) {
            auto l = n, r = n;
            result.push_back(s);
            for (;;) {
                if (s.back() == ')') --r;
                else if (l < r + 2) --l;
                else break;
                s.pop_back();
                if (s.empty()) return result;
            }
            
            s.back()=')';
            s.append(n - (l - 1), '(');
            s.append(n - (r + 1), ')');
        };
    }

  • 0
    N

    Can you explain your approach ?


  • 0
    H

    I got a "Memory Limit Exceeded" using this method


  • 0

    Nice solution! Thanks for sharing


  • 0
    J

    Python translation:

    class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        
        comp_list = [['']]
        
        for i in range(1,n+1):
            res = []
            
            for j in range(i):
                for left in comp_list[i-1-j]:
                    for right in comp_list[j]:
                        res.append( '(' + left + ')' + right)
                        
            comp_list.append(res)
    
        return comp_list[-1]

  • 0
    F

    Thank you for the solution. However, I guess it occupies great space as we need to maintain n lists from f(0) to f(n-1) to get the final f(n), doesn't it? Anyway, this solution provide me a new perspective to solve the problem and that's really helpful to me, thanks!


Log in to reply
 

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