Python and recursion


  • 0
    M

    Another function "pp" is used, to use recursion, and empty string s. In function "pp":

    • a,b are indices for whether the next character should be '(' or ')', respectively

    • i is index for current character

    • R stores the valid results, or solution

    • Recurse by decreasing a or b, and determine the next element in string

        class Solution(object):
            @staticmethod
            def pp(a,b,i,s,R):
            if a < 0 or a > b:
                return
            if a == 0 and b == 0:
                R.append(s)
            else:
                if a > 0:
                    t = list(s)
                    t[i] = '('
                    s = ''.join(t)
                    Solution.pp(a-1,b,i+1,s,R)
                if b > 0:
                    t = list(s)
                    t[i] = ')'
                    s = ''.join(t)
                    Solution.pp(a,b-1,i+1,s,R)
            return R
      
        def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
            s = ' '*2*n
            return Solution.pp(n,n,0,s,[])

Log in to reply
 

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