all articles

leetcode war 22 - Generate Parentheses

2017-10-10 @sunderls

leetCode js

https://leetcode.com/problems/generate-parentheses/description/

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

analysis

we've just used a stack to do parentheses validation in leetcode war 20 - Valid Parentheses, maybe we can do something similar.

first watch some real cases

for n = 1

  1. ()

for n = 2

we try to add a new pair, by placing first the left parenthesis

  1. (() => (())
  2. (() => (()) , same as 1
  3. ()( => ()()

seems this doesn't show us anything. now recall on the stack, in order to keep a stack alive, we only have to remember one thing

never push when there is no left parenthesis in the stack

thus we can use this strategy:

for n = 1

[]
['(']
['()']

for n = 2

[]
['(']
['((']  ['()']
['(())']  ['()()']

for n = 3

['(']
['((']  ['()']
['((('] ['(()']  ['()(']
['((()'] ['(()('] ['(()()'] ['()(('] ['()()']
['((())'] ['(()()'] ['(()())'] ['()(()'] ['()()(']
['((()))'] ['(()())'] ['(()()))'] ['()(())'] ['()()()']

trial 1 - keep track of the left parenthesis

in which we keep an array of result & the count of left parenthesis, in each round we shift the results and push them back in by checking unmatched count.

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    var result = [];

    var i = 0;
    var j = n * 2;
    var total = 0;
    var unmatchedLeftParenArr = [];
    var unmatchedCount = 0;
    var tmp = null;
    while (j > 0) {
        total = result.length;
        i = 0;

        if (total === 0) {
            result.push('(');
            unmatchedLeftParenArr.push(1);
        }

        while (i < total) {
            tmp = result.shift();
            unmatchedCount = unmatchedLeftParenArr.shift();

            // if left paren are all used
            if (unmatchedCount >= j) {
                result.push(tmp + ')');
                unmatchedLeftParenArr.push(unmatchedCount - 1);
            } else if (unmatchedCount > 0) { // if right/left paren is ok to push
                result.push(tmp + '(');
                unmatchedLeftParenArr.push(unmatchedCount + 1);

                result.push(tmp + ')');
                unmatchedLeftParenArr.push(unmatchedCount - 1);
            } else { // if only left paren is ok to push
                result.push(tmp + '(');
                unmatchedLeftParenArr.push(unmatchedCount + 1);
            }

            i += 1;
        }

        j -= 1;
    }

    return result;
};

it passed, but ranked only bottom 30%, need to improve. but how?

improvement 1 - throw out valid result quicker

to cut down time cost, when left paren got all used, we can throw the result more quickly

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    var finalResult = [];
    var result = [];

    var i = 0;
    var j = n * 2;
    var total = 0;
    var unmatchedLeftParenArr = [];
    var unmatchedCount = 0;
    var tmp = null;
    while (j > 0) {
        total = result.length;
        i = 0;

        if (total === 0) {
            result.push('(');
            unmatchedLeftParenArr.push(1);
        }

        while (i < total) {
            tmp = result.shift();
            unmatchedCount = unmatchedLeftParenArr.shift();

            // if only right paren can be pushed
            // throw result directly
            if (unmatchedCount >= j) {
                var str = tmp;
                while (unmatchedCount > 0) {
                    str += ')';
                    unmatchedCount -= 1;
                }
                finalResult.push(str);
            } else {
                result.push(tmp + '(');
                unmatchedLeftParenArr.push(unmatchedCount + 1);

                if (unmatchedCount > 0) { // if right paren is ok to push
                    result.push(tmp + ')');
                    unmatchedLeftParenArr.push(unmatchedCount - 1);
                }

            }

            i += 1;
        }

        j -= 1;
    }

    return finalResult.concat(result);
};

this ranked about 50%. still not good. it seems that some relation exists between n and n+1, how to do that?