Leetcode——有効括弧の組み合わせを生成する
1149 ワード
nは括弧を生成する対数を表します.可能なすべての有効な括弧の組み合わせを生成できるように関数を書いてください.
たとえば、n=3が与えられ、結果は次のようになります.
[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]
考え方:1.再帰的な考え方,すなわち深さ優先探索DFSは,合計2 n個の格子があると仮定し,各格子に2種類の探索結果があるため,時間的複雑度は2 n 2^{2 n}22 nであり,すべて探索された.2.上記の方法を改良し、上記区間のいずれかの位置において、左かっこ'(‘必ず右かっこ以上でなければ無効なかっこの組み合わせである'()')')ということはできないでしょう.
したがってDFSでは、統計的に左かっこの個数がn未満であれば、'('を加えればよいが、再帰的に、左かっこの数が右かっこの数より大きく、右かっこの数がn未満であれば')'を加えればよい.
最後に左右の括弧が残らない場合、つまり並ぶべきものはすべて並べ終わって、最後にresultを得ます.
コード:
たとえば、n=3が与えられ、結果は次のようになります.
[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]
考え方:1.再帰的な考え方,すなわち深さ優先探索DFSは,合計2 n個の格子があると仮定し,各格子に2種類の探索結果があるため,時間的複雑度は2 n 2^{2 n}22 nであり,すべて探索された.2.上記の方法を改良し、上記区間のいずれかの位置において、左かっこ'(‘必ず右かっこ以上でなければ無効なかっこの組み合わせである'()')')ということはできないでしょう.
したがってDFSでは、統計的に左かっこの個数がn未満であれば、'('を加えればよいが、再帰的に、左かっこの数が右かっこの数より大きく、右かっこの数がn未満であれば')'を加えればよい.
最後に左右の括弧が残らない場合、つまり並ぶべきものはすべて並べ終わって、最後にresultを得ます.
コード:
class Solution:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
self.list = []
self._gen(0, 0, n, "")
return self.list
def _gen(self, left, right, n, result):
if left == n and right == n: # 2n ,n
self.list.append(result)
return
if left < n:
self._gen(left + 1, right, n, result + "(")
if left > right and right < n:
self._gen(left, right + 1, n, result + ")")