ワイルドカード文字「?」を置き換えることによって形成されたバランスのとれた括弧文字列をすべて出力します。

バランスの取れた括弧とは、括弧の文字列がある場合、各開き括弧に対応する閉じ括弧があり、括弧のペアが正しくネストされていることを意味します。文字列のサイズは偶数である必要があります。この問題では、文字 '?' を含む括弧文字列が与えられ、私たちのタスクは、'?' を適切な括弧で置き換えることによって、可能なすべてのバランスのとれた括弧文字列を形成することです。指定された文字列では、括弧「(」と「)」のみが使用されています。

例例

リーリー

説明

の中国語訳は次のとおりです:

説明

「?」を置き換えることで形成できるのは、バランスの取れた文字列のみです。

リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

バランスの取れた弦を形成するには 2 つの方法があります。

• 1 つの方法は、インデックス 0、1、2 を開き括弧に置き換え、他のインデックスを閉じ括弧に置き換えることです。

• 2 番目の方法は、インデックス 0、1、および 3 を開き括弧に置き換え、その他のインデックスを閉じ括弧に置き換えることです。

• 3 番目の方法は、インデックス 0、1、4 を開き括弧に置き換え、その他のインデックスを閉じ括弧に置き換えます。

• 4 番目の方法は、インデックス 0、2、および 3 の位置を開き括弧に置き換え、他のインデックスの位置を閉じ括弧に置き換えます。

• 最後の方法は、インデックス 0、2、4 を左括弧に置き換え、その他のインデックスを閉じ括弧に置き換えることです。

＃＃＃方法＃＃＃

上記で指定された文字列の例を見てきました。次のステップに進みましょう -

バックトラッキング手法を使用してこの問題を解決できます。

この方法については以下で説明します -

まず、'create' という関数を初期化し、'?' を括弧で置き換えた後、パラメーター str とindex = 0 を使用して、考えられるすべての文字列を作成します。
この関数では、

• −> まず、基本的な条件を設定します。文字列の終わりに達したら、その文字列を「check」関数に渡して、文字列のバランスが取れているかどうかを確認する必要があります。バランスが取れている場合は、文字列を出力します。

−>文字列の現在の文字が「?」の場合、

まず、これを開き括弧に置き換え、同じ関数を呼び出して文字列の終わりに達したかどうかを確認します。

次に、これを右括弧に置き換えて、同じ関数を再度呼び出して、文字列の終わりに達したかどうかを確認します。

最後に、文字列をバックトラックして、現在の文字を「?」に割り当てます。

−> それ以外の場合、文字列の現在の文字が括弧の場合は、同じ関数を呼び出して次のインデックスに移動します。

「check」関数を初期化して、文字列のバランスが取れているかどうかを確認します。

• -> この関数では、スタックを初期化してから、
をチェックします。

−> 文字列の最初の文字が右括弧の場合、false

を返します。

-> 現在の括弧が閉じている場合、2 つの状況があります: スタックが空の場合、対応する開いた括弧がないため false が返されます。それ以外の場合は、対応する開き括弧をスタックからポップします。

−> 最後に、スタックが空かどうかを確認します。空の場合は、文字列のバランスが取れていることを意味し、true を返します。それ以外の場合は、括弧がいくつか残っているため、文字列のバランスが取れていないことを意味し、false を返します。

Example

の中国語訳は次のとおりです:

Example

以下は、すべてのバランスのとれた文字列を取得するために上記のバックトラッキング方法で使用される C コードです。 リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量と空間計算量

文字列をバックトラックする必要があるため、上記のコードの時間計算量は O(N*(2^N)) です。

ブラケットをスタックに保存するため、上記のコードの空間複雑さは O(N) です。

ここで、N は文字列のサイズです。

＃＃＃結論は＃＃＃

このチュートリアルでは、ワイルドカード文字「?」を置き換えることによって形成できるすべてのバランスのとれた括弧文字列を出力するプログラムを実装しました。バックトラッキング方式を導入しました。時間計算量は O(N*(2^N)、空間計算量は O(N) です。ここで、N は文字列のサイズです。

以上がワイルドカード文字「?」を置き換えることによって形成されたバランスのとれた括弧文字列をすべて出力します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。