Python Non-Recursive solution


  • 0
    C

    Well, read the code...

    class Solution(object):
        def generateParenthesis(self, n):
            """
            :type n: int
            :rtype: List[str]
            starting from a right bracket at the end
            and always ends with a left bracket front
            """
            
            
            # curr_s, n_left, n_bal
            combs = [["(", n-1, 1]]
            for i in range(2*n):
                new_items = []
                for comb in combs:
                    
                    slot_left = 2 * n - len(comb[0])
                    # spawn a new record with right bracket added if allows
                    # 1. there are left brackets left to fill
                    # 2. there are more slots to fit in pairs where n_pair = 2 * n_leftbracket_left
                    # 3. there are left brackets in the current string left to be balanced
                    if (comb[1] > 0 and 2 * comb[1] < slot_left and comb[2] > 0):
                        new_items.append([comb[0] + ")", comb[1], comb[2] - 1])
                        
                    # add a left bracket to this original one if n_left allows
                    if (comb[1] > 0):
                        comb[0] += "("
                        comb[1] -= 1
                        comb[2] += 1
                    elif (len(comb[0]) < 2*n):
                        # otherwise this string is done by appending the rest of the slots with right bracket
                        comb[0] += ")" * slot_left
    
                if new_items:
                    combs += new_items
            return [comb[0] for comb in combs]
    
    if __name__ == '__main__':
        sol = Solution()
        print(sol.generateParenthesis(3))
    

Log in to reply
 

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