CODEWITHSUNDEEP
pythonpython-3.xrecursion
Krishna Aswani
Krishna Aswani

Reputation: 311

Generate Parentheses Recursion passing as list vs string

I was solving the Generate Parenthesis question in leetcode. If I use the below code (cur as a list to append):

Here f is counter for forward brackets and b is a counter for backward brackets. 

def generateParenthesis(n: int) -> List[str]:

    def recursion(f, b, cur=[]):

        if len(cur)==(n*2):
            a ="".join(cur)
            output.append(a)
            return
        if f:
            cur.append("(")
            recursion(f-1,b, cur)
        if b:
            cur.append(")")
            recursion(f,b-1, cur)
    output = []
    f = n
    b = n
    recursion(f, b, cur)

    return output

When I run the above solution I get the output as for n =3:

["((()))"]

if instead of appending to a list, I use cur as a string and add "(" to it I get the right answer.

def generateParenthesis(n: int) -> List[str]:

    def recursion(f, b, cur=""):

        if b < f or b<0 or f<0:
            return

        if len(cur)==n*2:
            output.append(cur)
            return
        if f:
            recursion(f-1,b, cur+"(")
        if b:
            recursion(f,b-1, cur+")")


    output = []
    f = n
    b = n
    recursion(f, b)

    return output

This produces the current output which is:

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

I know strings are immutable so adding "(" to string is O(N). I was just trying to avoid that. Can anyone help me understand what is going on here and if/how can we use the first code in the right way. I think it has to do with using a separate list (variable named cur) in each recursion.

Upvotes: 0

Views: 300

Answers (2)

Tony
Tony

Reputation: 51

First of all, I don't like the syntax for -> List[str]: and recursion(f, b, cur), as List is not defined in the code and cur is not defined in the area as well.

Now let's look at your code in the first section.

def generateParenthesis(n: int) -> List[str]:

    def recursion(f, b, cur=[]):

        if len(cur)==(n*2):
            a ="".join(cur)
            output.append(a)
            return
        if f:
            cur.append("(")
            recursion(f-1,b, cur)
        if b:
            cur.append(")")
            recursion(f,b-1, cur)
    output = []
    f = n
    b = n
    recursion(f, b, cur)

    return output

The variable cur in passed into the recursions by reference. That means, all called recursions share the same cur variable. So in the execution, once "((()))" generated, the other recursions will still increase the length of cur, making "((()))" the only output. So if you . change the condition to if len(cur) >= n*2, you will get the below ouput.

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

To make your code working, a naive way is to create a new list every time you call the recursion. For example, recursion(f-1, b, deepcopy(cur)), where deepcopy is from copy import deepcopy. But I believe you would rather use the immutable string in this case.

On the other hand, you can also see the list as a stack. Every recursion call, you append a parenthesis, meaning you push a parenthesis in the stack. Therefore, you should also pop out the pushed parenthesis after the recursion call. Although in this case, your previous checking condition should be used.

Since Python's list is something similar to C++'s vector, we can just maintain the index of our last element instead of actual popping out. The code after modification should be

def generateParenthesis(n):

    def recursion(f, b, cur=[None] * (2*n), idx= 0):

        if b < f or b<0 or f<0:
            return

        if idx >= (n*2):
            a ="".join(cur)
            output.append(a)
            return
        if f:
            cur[idx] = "("
            recursion(f-1,b, cur, idx + 1)
        if b:
            cur[idx] = ")"
            recursion(f,b-1, cur, idx + 1)

    output = []
    f = n
    b = n
    recursion(f, b)

    return output

And let's do print(generateParenthesis(3)), we get

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

Good.

PS: Python doesn't have a native linkedlist but has a native deque (https://docs.python.org/3/library/collections.html#collections.deque), you may use this data structure when a more complicated push and pop is needed.

Upvotes: 1

cdlane
cdlane

Reputation: 41903

I know strings are immutable so adding "(" to string is O(N). I was just trying to avoid that.

But the interesting part is your string solution is 25% faster than @Tony's mutable list-based solution! At least with my timings of generateParenthesis(13).

Below's my string-based solution -- it's about 15% slower than @Tony's but has no side effects and can be converted to a(n even slower) list-based solution without dangerous defaults. I.e. you can move the inner recursive function to its own top level function and it will still work:

def parenthesis(n):

    def parenthesis_recursive(k, f, b, current=""):
        if not b >= f >= 0 <= b:
            return []

        if len(current) == k:
            return [current]

        return parenthesis_recursive(k, f - 1, b, current + "(") + parenthesis_recursive(k, f, b - 1, current + ")")

    return parenthesis_recursive(n * 2, n, n)

print(parenthesis(3))

Upvotes: 1

Related Questions