参考资料:https://www.youtube.com/watch?v=sz1qaKt0KGQ

DFS总结:

一般DFS:

def fun()

  DFS()

def DFS()

  if:

  DFS

带回溯的DFS:

 

def fun()

  DFS()

def DFS()

  if:

    ret.append()
  DFS

  onecase.pop()
#注意递归里要写成这样
if left > 0:self.DFS(ret, n, left -1, right, onecase + \'(\')
if right > 0:self.DFS(ret, n, left, right -1, onecase + \')\')


#不是这样 这样会丢失中间子树的右节点。
if left > 0:
    left -= 1
    onecase = onecase + \'(\'
    self.DFS(ret, n, left, right, onecase)
while right > 0:    #if will lose some right branch such as \'(())\'
    right -= 1
    onecase = onecase + \')\'
    self.DFS(ret, n, left, right, onecase)

回到题目上:

 

树生成策略:

  )不能位于开头 [left == n right =n -1]

  只有在前面有( 没有被匹配的时候(left大于right)的时候 才能加上 )[if left – right >0 append(\’)\’]

  不能只剩下( (left大于零 right 等于0)[left >0 right ==0]

  当left==0而right>0时,把所有的右括号都加上然后递归

盯着题目发了半小时呆,决定去查U2B。真是会了5分钟不会半小时啊.

 

Runtime: 64 ms, faster than 10.05% of Python3 online submissions forGenerate Parentheses.
Memory Usage: 13 MB, less than 90.88% of Python3 online submissions forGenerate Parentheses.
 

Submission Detail

8 / 8 test cases passed.
Status: 

Accepted

Runtime: 64 ms
Memory Usage: 13 MB
Submitted: 0 minutes ago

 

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ret = []
        # 0
        if n == 0:
            return ret
        # 1
        if n == 1:
            ret.append(\'()\')
            return ret
        # general
        # left:number of \'(\'     right:number of \')\' 
        onecase = \'\'
        self.DFS(ret, n, n, n, onecase)
        return ret

    def DFS(self, ret, n, left, right, onecase):
        # #cut tree
        if (left ==n and right ==n-1) or (left >0 and right ==0) or (left > right):
            return
        #ret ahead
        if left ==0 and right >0:
            onecase = onecase + \')\'*right
            right = 0
            if ret.count(onecase) == 0:
                ret.append(onecase)
        #ret
        if left ==0 and right ==0:
            if ret.count(onecase) ==0:
                ret.append(onecase)
        #
        if left > 0:self.DFS(ret, n, left -1, right, onecase + \'(\')
        if right > 0:self.DFS(ret, n, left, right -1, onecase + \')\')

 

 

ver2:

Runtime: 36 ms, faster than 98.00% of Python3 online submissions forGenerate Parentheses.
Memory Usage: 13.3 MB, less than 71.53% of Python3 online submissions for Generate Parentheses.
 

Submission Detail

8 / 8 test cases passed.
Status: 

Accepted

Runtime: 36 ms
Memory Usage: 13.3 MB
Submitted: 5 minutes ago

 

复制代码
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        #0
        if n ==0:
            return []
        #1
        if n==1:
            return["()"]
        #normal
        ret = []
        onecase = \'\'
        self.DFS(ret,n,n,onecase)
        return ret
    def DFS(self,ret,left,right,onecase):
            if left > right:
                return
            if left ==0 and right ==0:
                ret.append(onecase)
            if left >0:self.DFS(ret,left -1,right,onecase + \'(\')
            if right >0:self.DFS(ret,left,right -1,onecase + \')\')
复制代码

 

版权声明:本文为alfredsun原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/alfredsun/p/10941342.html