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


  • 1
    S

    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]:
                temp.append('('+curr+')') 
                temp.append('()'+curr)
                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
    T

    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.