Python wrong answer


  • 0
    M

    I am using python for this problem and get to the following code. I run it on my computer in both python 2.7 and 3.4 and get at least correct answer for input 2. However, the OJ said my output is wrong:

    Submission Result: Wrong Answer

    Input: 2
    Output: ["()","()()","(())"]
    Expected: ["(())","()()"]

    Code:

    class Solution:
      # @param an integer
      # @return a list of string
      ret = set()
      def helper(self, left, right, s):
          if (left < 0 or right < 0 or left > right):
              return
          if (left == 0 and right == 0):
              self.ret.add(s)
              return
          self.helper(left - 1, right, s + '(')
          self.helper(left, right - 1, s + ')')
          return
        
            
      def generateParenthesis(self, n):
          self.helper(n, n, '')
          return list(self.ret)
    

    Anyone has any ideas?


  • 0
    D

    Don't use ret as a class member, just use it like local value, the result will be correct like my code:

    class Solution:
    # @param an integer
    # @return a list of string
    def generateParenthesis(self, n):
        res = []
        if n <= 0:
            return res
        self.backtrack(res, '', n, n)
        return res
    
    def backtrack(self, res, item, left, right):
        if (left > right or left < 0 or right < 0):
            return
        elif (left == 0 and right == 0):
            res.append(item)
            return
        self.backtrack(res, item+'(', left-1, right)
        self.backtrack(res, item+')', left, right-1)
    

    Or you have to initial ret at main function, otherwise, it will contain last time result.

    class Solution:
    # @param an integer
    # @return a list of string
    res = []
    def generateParenthesis(self, n):
        self.res = []
        if n <= 0:
            return self.res
        self.backtrack('', n, n)
        return self.res
    
    def backtrack(self, item, left, right):
        if (left > right or left < 0 or right < 0):
            return
        elif (left == 0 and right == 0):
            self.res.append(item)
            return
        self.backtrack(item+'(', left-1, right)
        self.backtrack(item+')', left, right-1)

Log in to reply
 

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