4-7 lines Python


  • 100

    p is the parenthesis-string built so far, left and right tell the number of left and right parentheses still to add, and parens collects the parentheses.

    Solution 1

    I used a few "tricks"... how many can you find? :-)

    def generateParenthesis(self, n):
        def generate(p, left, right, parens=[]):
            if left:         generate(p + '(', left-1, right)
            if right > left: generate(p + ')', left, right-1)
            if not right:    parens += p,
            return parens
        return generate('', n, n)
    

    Solution 2

    Here I wrote an actual Python generator. I allow myself to put the yield q at the end of the line because it's not that bad and because in "real life" I use Python 3 where I just say yield from generate(...).

    def generateParenthesis(self, n):
        def generate(p, left, right):
            if right >= left >= 0:
                if not right:
                    yield p
                for q in generate(p + '(', left-1, right): yield q
                for q in generate(p + ')', left, right-1): yield q
        return list(generate('', n, n))
    

    Solution 3

    Improved version of this. Parameter open tells the number of "already opened" parentheses, and I continue the recursion as long as I still have to open parentheses (n > 0) and I haven't made a mistake yet (open >= 0).

    def generateParenthesis(self, n, open=0):
        if n > 0 <= open:
            return ['(' + p for p in self.generateParenthesis(n-1, open+1)] + \
                   [')' + p for p in self.generateParenthesis(n, open-1)]
        return [')' * open] * (not n)

  • 5
    J

    I thought I know Python...

    So, could you please tell me how could I get these advanced skills.


  • 36

    I learned a lot by reading tutorials/docs and by looking at solutions of others at checkio.org (a Python programming site) and by spending a month on Python topics at Stackoverflow. Also, practice practice practice :-)


  • 0
    J

    Thanks for your kind replying, I will keep learning with your advances.


  • 0
    C

    Your program is very good, and I want to ask you some question. In solution 1, after line 3, the variable parens is not used as parameter of "generate(p + '(', left-1, right)", and why dose after this function the variable parens change?


  • 2

    @jh3 It's a default argument, so I don't have to explicitly provide it, and it's the same object for all calls. Here's some explanation that might help.


  • 0
    C

    I am very grateful for your answer, and I have understood. Thank you very much!


  • 0
    G

    WOW,you are quite familiar with python! Nice solutions!


  • 0
    T

    abs fantastic, recursive and ifs together. you are the man, MAN!!!


  • 0
    E

    I notice the comma is needed in the first solution. Can you explain the trick there?


  • 0

    @erkangxu Makes it a tuple so it's equivalent to parens.append(p).


  • 1
    W

    what are the time and space complexity?


  • 0
    I
    This post is deleted!

  • 0

    I change your recursion solution 1 to make it even shorter.
    I don't define another sub function.
    By the way, self.generateParenthesis is too long.

    def generateParenthesis(self, n, left=0, right=0, cur=''):
            if left == n: return [cur + ')' * (n - right)]
            if left == right: return self.generateParenthesis(n, left + 1, right, cur + '(')
            return self.generateParenthesis(n, left + 1, right, cur + '(') \
                + self.generateParenthesis(n, left, right + 1, cur + ')')
    

    Find more here: https://discuss.leetcode.com/topic/79447/3-lines-recursion-solution


  • 0
    S

    your response "practice,practice,practice'' give me hope, thanks


  • 3
    A

    For solution 1:
    I think the most import trick is that the default argument value is execute at define time, not runtime.

    So, in this case, every changes to parens in each recursive call, will change the same list, that's why the parena will includes all the possible result.

    Nice code! You are really familiar with python.


  • 0
    F

    Haha, I actually use your every solution as the optimal solution to every problem on LC.
    Thank you dude, for your good work!


  • 0
    H

    @StefanPochmann Could you please explain how the third solution works? I can't figure it out...


  • 0
    Y

    I guess this is so called genius!


  • 0
    C

    I thought I knew python.
    But this seems another python.
    Genius!


Log in to reply
 

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