- 334 名前：デフォルトの名無しさん mailto:sage [2023/06/07(水) 09:49:06.82 ID:Bta2HQ7X0.net]
- >>333
結論から言うと、それは難しい問題であり、一般的なアプローチでは、「全てのパターンを生成し、
それがバランスの取れた括弧列であるかどうかを判定する」という方法が用いられます。
しかし、バランスの取れた括弧列を生成するための一種の再帰的なパターンは存在します。
それは、大きさnの全てのバランスの取れた括弧列を生成した後で、その各々に対して以下の操作を行うことです：
1. '(' + P + ')' を追加する
2. P + '()' を追加する
3. '()' + P を追加する
ここで P は大きさnの任意のバランスの取れた括弧列です。
この操作を行うと、全ての大きさn+1のバランスの取れた括弧列を生成することができます。
ただし、これは重複する列を生成する可能性があるため、生成された列は一意であることを保証するために
何らかの方法で重複を除去する必要があります。
したがって、厳密には「全てのパターンを生成し、それがバランスの取れた括弧列であるかどうかを判定する」
という方法とは異なりますが、これは一種の再帰的なアプローチと言えます。
しかし、これらのアプローチは計算時間やメモリ使用量の観点から見ると、>>328に示されたDFSを用いたアプローチに比べて
効率的ではないかもしれません。また、DFSを用いたアプローチは明確に「正しい括弧の追加操作のみ」を行っていると言えます。
なぜなら、すべての括弧列を生成する過程で、同時にその列が正しい括弧列であるかどうかをチェックすることが可能だからです。
|
 |
