Use DP to solve the problem but, OJ say the answer is wrong

  • 1

    Here is the idea of the code, for
    If we know the list of string in N-1
    Then we can get N with
    '()' + x or '(' + x + ')' or x + '()' except there is a case if x like '()()', we just need to avoid this duplication
    Here is my code

    class Solution:
    # @param {integer} n
    # @return {string[]}
    def generateParenthesis(self, n):
        if n <= 0:
            return []
        result = {}
        result[1] = ['()']
        if n == 1:
            return result[1]
        for i in xrange(2, n+1):
            temp = []
            for curr in result[i-1]:
                if curr != '()'* (i-1):
                    temp.append(curr+ '()')
            result[i] = temp
        return result[n] 

    For test case 4, my answer are the same as OB, but order is different.

    Here is my result for n=4

    ['(((())))', '()((()))', '((()))()', '(()(()))', '()()(())', '()(())()', '((())())', '()(())()', '(())()()', '((()()))', '()(()())', '(()())()', '(()()())', '()()()()']

  • 1

    I followed the same approach as you and a quick check on the n=4 testcase made me realize that the expected result contained following structure (())(()), which basically cannot be produced (or at least not without further enhancement) by the DP approach. Therfore I just went with the backtracking approach.

Log in to reply

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