Easy to understand Python memoization solution

  • 0

    This solution uses a lot of extra space for memoization, but it's really easy to understand, compared to solutions which operate with individual '(' and ')'.
    Idea: to get answer for N, get answers for 1..N-1 and combine them in various ways.
    Sets make sure that we're not duplicating solutions.

    class Solution(object):
        def recur(self, n):
            if self.res.has_key(n):
                return self.res[n]
            res_prev = self.recur(n-1)
            res = set()
            for x in res_prev:
                res.add("(" + x + ")")
            for lvl in xrange(1, n):
                res_prev1 = self.recur(lvl)
                res_prev2 = self.recur(n-lvl)
                for x in res_prev1:
                    for y in res_prev2:
                        res.add(x + y)
                        res.add(y + x)
            self.res[n] = res
            return res
        def generateParenthesis(self, n):
            self.res = {0: set(), 1: set(["()"])}
            return list(self.recur(n))

Log in to reply

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