Python long iterative solution (non-recursive)


  • 0
    class Combo(object):
        def __init__(self, _rightMiss, _s, _leftReserve):
            self.rightMiss = _rightMiss
            self.s = _s
            self.leftReserve = _leftReserve
    
    class Solution(object):
        def generateParenthesis(self, n):
            """
            :type n: int
            :rtype: List[str]
            """
            left = "("
            right = ")"
            comboList = []
            result = []
            rightCount = 0
            while 1:
                newCombos = []
                finishedMark = 0
                if len(comboList) == 0:
                    comboList.append(Combo(1, left, n-1))
                else:
                    for combo in comboList:
                        if combo.rightMiss == 0:
                            if combo.leftReserve > 0:
                                combo.rightMiss += 1
                                combo.s += left
                                combo.leftReserve -= 1
                            else:
                                finishedMark += 1
                        else:
                            if combo.leftReserve > 0:
                                newCombo = Combo(combo.rightMiss, combo.s, combo.leftReserve)
                                combo.rightMiss += 1
                                combo.s += left
                                combo.leftReserve -= 1
                                newCombo.rightMiss -= 1
                                newCombo.s += right
                                newCombos.append(newCombo)
                            else:
                                while combo.rightMiss > 0:
                                    combo.rightMiss -= 1
                                    combo.s += right
                for c in newCombos:
                    comboList.append(c)
                if finishedMark == len(comboList):
                    break
                            
            for c in comboList:
                result.append(c.s)
            return result
    

    Use the Combo class to keep track of current string, for each string combination, there can be up to two choices in each round.
    I think recursion is better for this problem...


Log in to reply
 

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