DEV Community

kevin074
kevin074

Posted on

Leetcode diary: 22. Generate Parentheses [DFS]

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

This is definitely easy of medium question, could be marked easy honestly.

I am having major depression and confidence fell into abyss from trying to do a hard problem. Wanted to do a trilogy of it, since there are 3 of the similar premise problem. Alas I was only able to do the medium questions and come to nothing close to the solution for the hard level problem. Woe is me, fuck it I'll just do something that I know would be easy just from reading the title of the problem.

This is a simple "generate all" type of question. Whenever you see a problem like this the go-to strategy is DFS. The question asks to generate all valid parenthesis. If you aren't familiar with parenthesis questions, just know that the only restriction is that you always have to have at least 1 more left parenthesis than right before you add a right parenthesis.

Therefore the thought process for this question is:
1.) use DFS somehow
2.) keep track of left and right parenthesis number via ints
3.) as you use DFS to generate the "tree", just check for left > right before calling recursion adding the right parenthesis
4.) another condition to stop adding left parenthesis once left === 0;
5.) the end condition is when both left and right === 0, at this point you add the parenthesis permutation to the answer array.

code:

var generateParenthesis = function(n) {
    const answer = [];
    const left = n;
    const right = n;

    function recur (left, right, current) {
        if(left === 0 && right ===0) {
            answer.push(current.join(""));
            return;
        }

        if(left > 0) {
            recur(left-1, right, current.concat(["("]))
        }
        if(right > left) {
            recur(left, right-1, current.concat([")"]))
        }
    }

    recur(n,n,[])
    return answer;
};
Enter fullscreen mode Exit fullscreen mode

slight optimization is to use strings to for the current variable instead of array then current.join; no major difference in the algorithm from the fastest solution.

I don't know how much difference does it make, but at interviews it'll probably be a bonus when you mention that you recognize this as a tree-generating problem.

Next time I'll be back with the trilogy after I fought off my crippling depression from trying to solve it ;( ... don't call the cops on me thanks :D ...

Let me know anything on your mind after reading through this, THANKS!

Discussion (0)