leetcode with python:22. Generate Parentheses

题目:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

给定一数n,回传所有n个括号的排列可能(括号需有对应,像")("就不行)

我发现只要在n-1个括号的所有排列可能里所有的"("后加上"()"
再特别考虑"()()()..."这种可能,就考虑到了n个括号的所有排列可能
ex:n=2,所有可能会是["()()"和"(())"]
"()()"=>"(())()","()(())"
"(())"=>"(()())","((()))"
特别考虑=>"()()()"
而n=3的所有可能即为["((()))","(()())","(())()","()(())","()()()"]

class Solution:    def generateParenthesis(self, n: int) -> List[str]:        ans=["()"]                for i in range(n-1):            temp=[]            temp.append(ans[0]+"()")            for j in range(len(ans)):                for k in range(len(ans[j])):                    if ans[j][k]=="(":                        t=ans[j][0:k+1]+"()"+ans[j][k+1:len(ans[j])]                        if t not in temp:                            temp.append(t)            ans=temp                         return ans

以初始阵列["()"]出发推断出后续可能
第一项固定放"()()()...."类型的组合
所以先将纪录前一次所有可能的阵列(ans)的第一项后加上"()"
放入纪录此次所有可能的阵列(temp)

接着将ans内里所有元素一一操作
在"("后加上"()"放入temp内
但为防止重複纪录,先确认该可能不在temp内后再加入
完全执行完后将ans变为temp,进入下一次迴圈
迴圈执行结束后回传ans
最后执行时间114ms(faster than 5.07%)

然而我的解法效率低落,于是我开始浏览讨论区
看到了下面这个解法

class Solution:    def generateParenthesis(self, n: int) -> List[str]:        ans=[]        temp=[]                def x(opencnt,closecnt):            if opencnt==closecnt==n:                ans.append("".join(temp))                return                        if opencnt<n:                temp.append("(")                x(opencnt+1,closecnt)                temp.pop()                            if closecnt<opencnt:                temp.append(")")                x(opencnt,closecnt+1)                temp.pop()                x(0,0)        return ans

是个递迴解,纪录目前使用的"("和")"个数来继续推测接下来的可能

我们最多可以使用n个"("和n个")"来排列可能
而排列过程中绝不能使")"的使用次数(closecnt)超过"("的使用次数(opencnt)
否则会造成不合理的组合出现(如:")(","())(()")

所以当我们决定下一个括号要排什么时
只要opencnt< n我们下一项就可以选择放"("
而当closecnt< opencnt我们又多了")"可以选择

函式(x)需要的输入资料即opencnt和closecnt
当前的排列顺序都记录在temp
当opencnt==closecnt==n时,代表这时temp内装的是其中一种可能
将其透过join变为字串后放入ans,return

而当opencnt< n,我们选择放"("至temp内
往下执行x(opencnt+1,closecnt)继续探索此排列之后的可能
执行结束后将刚填入的"("pop掉(此排列之后的可能已全部被探索且记录)

而又当closecnt< opencnt,我们选择放")"至temp内
往下执行x(opencnt,closecnt+1)继续探索此排列之后的可能
执行结束后将刚填入的")"pop掉(此排列之后的可能已全部被探索且记录)

执行x(0,0),结束后ans内已有所有n个括号的排列可能
回传ans
最后执行时间34ms(faster than 95.21%)

那我们下题见