leetcode/javascript/0022-generate-parentheses.js at main · buzz-language/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/**
 * DFS
 * Time O(((4^N) / (N * SQRT(N)))) | Space O(((4^N) / (N * SQRT(N))))
 * Time O(2^N) | Space O(2^N)
 * https://leetcode.com/problems/generate-parentheses
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = (n) => dfs(n);

const dfs = (n, combos = [], open = 0, close = 0, path = []) => {
    const isBaseCase = path.length === n * 2;
    if (isBaseCase) {
        combos.push(path.join('')); /* Space O(N + N) */

        return combos;
    }

    const isOpen = open < n;
    if (isOpen)
        backTrackOpen(
            n,
            combos,
            open,
            close,
            path,
        ); /* Time O(2^N) | Space O(2^N) */

    const isClose = close < open;
    if (isClose)
        backTrackClose(
            n,
            combos,
            open,
            close,
            path,
        ); /* Time O(2^N) | Space O(2^N) */

    return combos;
};

const backTrackOpen = (n, combos, open, close, path) => {
    path.push('('); /* Space O(N) */
    dfs(n, combos, open + 1, close, path); /* Time O(2^N) | Space O(2^N) */
    path.pop();
};

const backTrackClose = (n, combos, open, close, path) => {
    path.push(')'); /* Space O(N) */
    dfs(n, combos, open, close + 1, path); /* Time O(2^N) | Space O(2^N) */
    path.pop();
};

/**
 * BFS
 * Time O(((4^N) / (N * SQRT(N)))) | Space O(((4^N) / (N * SQRT(N))))
 * Time O(2^N) | Space O(2^N)
 * https://leetcode.com/problems/generate-parentheses
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = (n) => bfs(n);

const bfs = (n, combos = []) => {
    const queue = new Queue([['', 0, 0]]);

    while (!queue.isEmpty()) {
        /* Time O(2^N) */
        const [str, open, close] = queue.dequeue();

        const isBaseCase = open === n && close === n;
        if (isBaseCase) {
            combos.push(str); /* Space O(N) */

            continue;
        }

        const isOpen = open < n;
        if (isOpen)
            queue.enqueue([`${str}(`, open + 1, close]); /* Space O(2^N) */

        const isClose = close < open;
        if (isClose)
            queue.enqueue([`${str})`, open, close + 1]); /* Space O(2^N) */
    }

    return combos;
};

/**
 * DFS
 * Time O(((4^N) / (N * SQRT(N)))) | Space O(((4^N) / (N * SQRT(N))))
 * Time O(2^N) | Space O(2^N)
 * https://leetcode.com/problems/generate-parentheses
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = (n, combos = []) => {
    const isBaseCase = n === 0;
    if (isBaseCase) {
        combos.push('');

        return combos;
    }

    for (let c = 0; c < n; c++) {
        for (const left of generateParenthesis(c)) {
            for (const right of generateParenthesis(n - 1 - c)) {
                combos.push(`(${left})${right}`);
            }
        }
    }

    return combos;
};