Python DP solution beating 100%, with explanation


  • 1
    Y
    class Solution(object):
        dp = {0:[""], 1:["()"]}
        def generateParenthesis(self, n):
            """
            :type n: int
            :rtype: List[str]
            """
            for i in xrange(len(self.dp), n + 1):
                self.dp[i] = []
                for j in xrange(i):
                    for i_str in self.dp[j]:
                        for o_str in self.dp[i-1-j]:
                            self.dp[i].append("(" + i_str + ")" + o_str)
            
            return self.dp[n]
    

    The self.dp will save all combinations for n.
    Each time we need to add a new parenthesis pair, we have to add "(" in the first position, as if we add it in the middle, we will have repeats. For example
    1 pair ( 1 pair ) 1 pair will be equal to () 3 pairs.

    The next question is where to put the ")". We loop through the possibilities, of the number of parenthesis pairs inside it. Then we loop through all the possible inner strings (i_str) and outer strings (o_string), append the concatenated string into self.dp

    Finally, return self.dp[n]


Log in to reply
 

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